首页 > 剑指offer > 二分查找-你能完全正确吗?
2014
03-31

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

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

tt

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

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

应该是有两处bug:

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

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

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

顺便给下完整的代码:

#include <stdio.h>

int binarySearch(int arr[], int l, int r, int x)
{
  while (l <= r)
  {
    int m = l + (r-l)/2;

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

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

    else r = m - 1; 
  }
  return -1; 
}

int main(void)
{
   int arr[] = {2, 3, 4, 10, 40};
   int n = sizeof(arr)/ sizeof(arr[0]);
   int x = 10;
   int result = binarySearch(arr, 0, n-1, x);
   (result == -1)? printf("Element is not present in array")
                 : printf("Element is present at index %d", result);
   return 0;
}

递归的实现:

int binarySearch(int arr[], int l, int r, int x)
{
   if (r >= l)
   {
        int mid = l + (r - l)/2;
        if (arr[mid] == x)  return mid;
        if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
        return binarySearch(arr, mid+1, r, x);
   }
   return -1;
}

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


  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  3. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?

  4. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;