二分查找的实现及注意事项

阳光穿透心脏的1/2处 2021-09-19 23:00 307阅读 0赞

听到二分查找，大家可能都会觉得它非常简单，从而会自然而然地忽略它。那么在实现这个看似简单的算法过程中有没有什么值得注意的地方呢？

下面是我写的一个二分查找的实现

int binary_search(int array[],int n,int value)
    {
        int begin = 0, end = n-1, mid = 0;
        bool flag =0;    //判断数据的排序方式，从小到大则为1，从大到小则为0
        for(int i = 0; i < n-1; ++i) //1
        {
            if(array[i] < array[i+1])
            {
                flag = 1;
                break;
            }
            if(array[i] > array[i+1])
            {
                flag = 0;
                break;
            }
        }
        
        if(flag)
        while(begin <= end)    //数据的排序方式，从小到大
        {
            mid = begin/2 + end/2;    //2
            if(array[mid] == value)
                return mid;
            if(array[mid] > value)
                end = mid - 1;        //3注意-1
            else
                begin = mid + 1;    //4注意+1
        }
        else
        while(begin <= end)    //数据的排序方式，从大到小
        {
             mid = begin/2 + end/2;
            if(array[mid] == value)
                return mid;
            if(array[mid] > value)
                begin = mid + 1;    
            else
                end = mid - 1;   
        }
        return -1;
    }

在这个程序中，我们需要注意的首先是注释1中的循环的作用，正如我们所知道的那样，二分查找要基于已经排好序的数组来实现，那么这个数组是按什么顺序来排列的呢，从大到小还是从小到大，这个循环的作用就是如此，通常它只会循环1到2次。因为不同的排序方式对查找失败后，调整缩小搜索范围的操作是不一样的，从上面的代码中也可以看出这点。为了让这个程序能对这两种排序方式的数组都适用，这个判断是必不可少的。

再来看看注释2的语句，mid为什么要等于begin/2 + end/2;而不是直接的（begin+end）/2;呢？在数学上这的确没有什么不同，但是在计算机里，却有很大的不同。设想你的数组很大，为方便说明，我以16位为例子，一个int型整数的最大值为65535，如果你的数组大小为40000，而你要需要查找的数据位于数组的比较后的位置，例如是下标为39800的那个数，那么在后面的查找中（begin+end）就会超出65535所能表示的范围，从而mid就会变成一个负数，这样你就永远都找不到你要找的数了，还可能发生内存错误。

再来看看注释3和注释4，很多人在缩小搜索范围时，都会把加1和减1漏了，这会导致一个什么的后果呢，就是这个程序可能会陷入死循环，这也是一个常有的错误。而为什么可以加1和减1，因为在查找失败时，mid肯定不会等于value，所以可以放心地从mid的下一个元素（加1）或mid的前一个元素（减1）开始查找。

如还有其他的注意事项和对程序有什么改进意见，还望各们指出！