二分查找程序.doc

《二分查找程序.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、二分查找      编程珠玑第4章中提到：虽然第一篇二分搜索论文在1946年就发表了，但是第一个没有错误的二分搜索策略却直到1962年才出现，由此可见二分查找思想虽然简单，但是要写好还是很难的。      那二分查找会出现那么多错误，主要是因为什么原因呢？边界问题         在二分查找的时候，边界很重要，需要理解查找的边界是什么？         边界主要可以分为[low,upper]，和[low，upper），即左闭右开、左闭右闭。这两种情况下，代码是不一样的，其不同可以参考下面的代码1./*

2、 2.    输入：A是待查找的非降序数组，n是数据的个数，key是查找的元素 3.    返回：没有key，返回-1，有返回在数据中的下标 4.*/  5.int binarySearch( int *A, int n, int key )  6.{  7.    int begin = 0;  8.    int end   = n;  9.    // [0,n) 左闭右开  10.    while ( begin < end )  11.    {  12.        int mid =

3、 begin + ( end - begin ) / 2;  13.        if ( A[mid] == key )  14.            return mid;  15.        else if ( A[mid] < key )  16.            begin = mid + 1;  17.        else // A[mid] > key    18.            end = mid;  19.    }  20.    return -1;  

4、21.}  这个是左闭右开，所以当key

5、  9.        if ( A[mid] == key )  1.            return mid;  2.        else if ( A[mid] < key )  3.            begin = mid + 1;  4.        else // A[mid] > key    5.            end = mid - 1;  6.    }  7.    return -1;  8.}  这个是左闭右闭，所以当key

6、ey在[begin,mid-1]之间 二分的优化问题1.    查找第一个出现的位置         如果查找的数在数据中出现多次，那么返回第一个出现的位置，这个剑指offer上的面试题38差不多，此处给出实现：1.// A范围是A[begin, end]为左闭右闭  2.int getFisrtOfK(int *A, int begin, int end, int key )  3.{  4.    if ( begin > end )  5.        return -1;  6.    in

7、t mid = begin + ( end - begin ) / 2;  7.    int midData = A[mid];  8.  9.    if ( midData ==  key )  10.    {  11.        if ( (mid == 0) 

8、

9、 A[mid-1] != key )  12.            return mid;  13.        else   14.            end = mid - 1;  15.    }  16.   

10、 else if ( midData < key )  17.        begin = mid  + 1;  18.    else // midData > key  19.        end = mid - 1;  20.  21.    return getFisrtOfK(A, begin, end, key);  22.}  当我们查找到A[mid]==key的时候，此时判断前一个数是否是key，如果不是key，那么此时mid就是第一