有坑的二分查找算法[]

2013-09-25

有坑的二分查找算法[求助]题目来源：http://blog.csdn.net/fox2790/article/details/834842722、下面的函数

有坑的二分查找算法[求助]
题目来源：http://blog.csdn.net/fox2790/article/details/8348427
22、下面的函数使用二分查找算法，对已按升序排序的数组返回所要查找数值的数据位置，请填写缺少的两句语句。

代码如下：


int* BinarySearch(int* arrayAddress, int arrayLength, int valueToSearch)
{
int head = 0;
int tail = arrayLength - 1;
int mid;

while (head < tail)
{
mid = (head + tail) / 2;
if (arrayAddress[mid] > valueToSearch)
{
_____(1)______
} 
else
{
_____(2)______
}
}

if (tail < arrayLength && arrayAddress[tail] == valueToSearch)
{
return &arrayAddress[tail];
} 
else
{
return NULL;
}
}

测试代码，如下


int main()
{
const int size = 8;
int arr[size] = { 6, 7, 8, 9, 10, 11, 12, 13 };
int* pi = BinarySearch(arr, size, 6);

if (pi != NULL)
{
cout << *pi << endl;
}
else
{
cout << "Not found!" << endl;
}
}

问了同学，有个答案，感觉不满意，如下
（1）tail = mid - 1;
（2）(arrayAddress[mid] == valueToSearch) ? (tail = head = mid) : (head = mid + 1);

哪位路过的高手有更好的答案，帮帮小弟吧！二分查找算法 c
[解决办法]


//就这么简单！！头每次加一，自己领悟吧！
tail=mid-1;
head+=1;

[解决办法]

引用:

如果是
引用
tail = mid - 1;
head = mid;

查找9时，BinarySearch(arr, size, 9)会出现死循环：
(1) head:0, tail:7, mid:3
(2) head:3, tail:7, mid:5
(3) head:3, tail:4, mid:3

(4) head:3, tail:4, mid:3（始终不变）
...
出现死循环。

程序跑过了，行不通。

我给的有问题。

题目中是对闭区间进行搜索，但是搜索的终止条件是区间只有一个元素。由于是向下取整，所以head = mid
可能导致死循环。

如果直接head = mid + 1会导致mid位置上满足条件的结果被忽略，所以对mid位置上的元素进行测试是必要的，如你在主贴中所说。对于填空题就只能这样了。

要避免死循环，就只有写成mid = (head + tail + 1) / 2了，这样的话是向上取整，mid永远不会和head等。
而tail可能是mid-1，这样就保证了进入下一次循环后搜索区间会减小，在1楼中的分析会保证正确性。

热点排行

C语言

有坑的二分查找算法[]