二分查找算法的一点改进

客官°小女子只卖身不卖艺 2022-04-25 00:58 147阅读 0赞

在计算机科学中，二分查找，是一种在有序数组中查找某一特定元素的搜索算法。这种搜索算法每一次比较都使搜索范围减半。第一篇二分查找的论文发表于1946年，然而第一个没有bug的二分查找算法却是在1962年才出现，中间用了16年时间。

本文首先二分查找算法给出了官方标准写法，然后给出另两种改进。主要原因是，当low和high对应的数组元素比较大时，求平均值可能会造成溢出，所以针对此做了一些改进。下面是相关代码实现。

//description: 给出二分查找法的几种C语言实现方法,其中第一种是官方写法，其它两种是改进
    //compile：gcc -g binary_search.c -o  binary_search
    //date： 2019-04-30
    
    #include <stdio.h>
    
    
    int binary_search_v1(int a[], int n, int k){
        int low, high, mid;
        low = 0;
        high = n-1;
        while(low <= high){
            mid = (low+high)/2;
            if(k<a[mid])
                high = mid-1;
            else if(k>a[mid])
                low = mid+1;
            else
                return mid;
        }
    
        return -1;
    }
    
    int binary_search_v2(int a[], int n, int k){
        int low, high, mid;
        low = 0;
        high = n-1;
        while(low <= high){
            //这里当low和heigh很大时，避免溢出
            mid = low+(high-low)/2;
            if(k<a[mid])
                high = mid-1;
            else if(k>a[mid])
                low = mid+1;
            else
                return mid;
        }
    
        return -1;
    }
    
    
    int binary_search_v3(int a[], int n, int k){
        int low, high, mid;
        low = 0;
        high = n-1;
        while(low <= high){
            //这里使用位运算效率更高
            mid = low+((high-low)>>1);
            if(k<a[mid])
                high = mid-1;
            else if(k>a[mid])
                low = mid+1;
            else
                return mid;
        }
    
        return -1;
    }
    
    
    int main() {
        int arr[] = {1,3,45,78,200,213,455};
        int size = sizeof(arr)/sizeof(int);
        int key = 213;
        int result1 = binary_search_v1(arr, size, key);
        int result2 = binary_search_v2(arr, size, key);
        int result3 = binary_search_v3(arr, size, key);
        printf("binary search result: %d, %d, %d\n", result1, result2, result3);
    
        return 0;
    }

运行截图如下：

![20190430110102810.png][]

参考文献

\[1\].https://www.toutiao.com/a6685490937977635341/

[20190430110102810.png]: /images/20220210/cd55aaa1a90f4cef9997b9f917199faa.png