Question

数据结构的题，谁会做啊，帮帮忙。。。。

设n个元素的有序表为ST，K为一个给定的值，二分查找算法如下：
int binsearch(stable ST, keytype K)
{ int low=1, high=ST.length, mid;
while(low <= high)
{ mid = (low+high)/2;
if(ST.elem[mid].key = = K) return mid;
if(K <ST.elem[mid].key) high = mid-1;
else low = mid+1;
}
return 0;
}
将上述算法语句high = mid-1改为 high = mid或将上述算法语句low = mid+1改为low = mid
（1）改动后，算法能否正常工作？请说明原因。
（2）若算法能正常工作，请给出一个查找序列和一个出错情况的查找键值。若能正常工作，请给出一个查找序列和查找某个键值的比较次数。

Answer 1

改动后不能正常工作：因为若最终只剩一个不匹配的数字时，此时将进入死循环。
例如序列只有一个数2查找3 。
此时low=1，high =1 符合条件 进入循环。
mid=1，此时显然两者不相等，所以high或者low依然等于1，进入死循环。

Answer 2

1）将high=mid-1改为high=mid:
low=mid+1可以正常使用，当查找值大于有序表中的最大值时，倒数第二步，high和low和mid都在有序表的最大值处，此时low=mid+1,low>high和标准格式一样返回查找失败，所以算法可以正常工作。同时当查找值在有序表中时也可以正常工作。
2）将low=mid+1改为low=mid:
high=mid-1可以正常使用，当查找值小于有序表中的最小值时，倒数第二步，high和low和mid都在有序表的最小值处，此时high=mid-1,low>high和标准格式一样返回查找失败，所以算法可以正常工作。同时当查找值在有序表中时也可以正常工作。
纯手输入的欢迎采纳。

Answer 3

不知道