二分查找-你能完全正确吗？

先给大家贴个题，热乎的，最新的阿里2014实习生笔试题(2014.3.29)。

很经典的二分查找，找出其中的bug。

题目让指出bug，我想应该是具体的说明错在哪，怎么错了。

应该是有两处bug:

1) while 循环处条件有错，如果只有一个元素，则返回的肯定的-1，导致答案错误。应改为 end >= start

2) 程序会进入死循环。考虑  start =1, end= 2. 假设 middle = 1. 若每次都执行 start=midlle, 即进入死循环。应改为 start = middle+1; end = middle-1;

另外，本题没有说已排序的数组是递增还是递减的。我在答题时又考虑了递减的情况，不算多余吧。

顺便给下完整的代码：

01	#include <stdio.h>

02

03	int binarySearch(int arr[], int l, int r, int x)

04

{

05	while (l <= r)

06

{

07	int m = l + (r-l)/2;

08

09	if (arr[m] == x) return m;

10

11	if (arr[m] < x) l = m + 1;

12

13	else r = m - 1;

14

}

15	return -1;

16

}

17

18	int main(void)

19

{

20	int arr[] = {2, 3, 4, 10, 40};

21	int n = sizeof(arr)/ sizeof(arr[0]);

22	int x = 10;

23	int result = binarySearch(arr, 0, n-1, x);

24	(result == -1)? printf("Element is not present in array")

25	: printf("Element is present at index %d", result);

26

return 0;

27

}

递归的实现：

01	int binarySearch(int arr[], int l, int r, int x)

02

{

03	if (r >= l)

04

{

05	int mid = l + (r - l)/2;

06	if (arr[mid] == x)  return mid;

07	if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);

08	return binarySearch(arr, mid+1, r, x);

09

}

10	return -1;

11

}

更多关于二分的问题请看无处不在的二分查找

评论

5 楼 dsjt 2014-04-02  

看了一下源码，是这样解决整数溢出的：

 int mid = (low + high) >>> 1;

4 楼 gaotong1991 2014-04-02  

timer_yin 写道

这个是什么编辑器啊

这个不是iteye的编辑器。WordPress里面的插件

3 楼 timer_yin 2014-04-02  

这个是什么编辑器啊

2 楼 gaotong1991 2014-04-02  

zhang_xzhi_xjtu 写道

其中隐藏最深的bug是(start+end)/2有可能上溢。
这个bug貌似是史上最著名的几个bug之一了。
能看出来说明对BS很熟悉，看不出来也不要紧，呵呵，这个bug本来就是隐藏在各种类库中很多年的。

所以这种写法 l + (r-l)/2; 是好一点的

1 楼 zhang_xzhi_xjtu 2014-04-01  

其中隐藏最深的bug是(start+end)/2有可能上溢。
这个bug貌似是史上最著名的几个bug之一了。
能看出来说明对BS很熟悉，看不出来也不要紧，呵呵，这个bug本来就是隐藏在各种类库中很多年的。