快速理解二分查找算法，附java代码实现

╰+攻爆jí腚メ 2024-04-01 19:17 24阅读 0赞

## 前言 ##

二分查找是一种常用的查找算法，其优点在于查找速度较快，最优时间复杂度为O（1），最坏时间复杂度也仅为O（log2n），在性能上十分优秀。  
二分查找必须对已排序的数组进行，因为其原理是不断比较区间的中位数与需要查找的值。一旦中位数大于查找值，则继续查找中位数与区间首（以下简称begin）的部分，反之，如果中位数小于查找值，则继续查找中位数与区间尾（以下简称end）的部分。

## 实现细节 ##

二分查找看似简单，但其实实现之时也有一些细节需要注意。  
首先是中位数的选择，大多数时候我们会直接用这样的代码：  
`int medium=(begin+end)/2 ;`  
其实这样会带来一些风险，例如begin和end超出int上限，如果数据较大时，这是需要注意的地方。  
其次，在设计二分查找的内部算法时，也需要注意中位数的选取。

上述代码，如后续设计不当，在查找到长度为2的子区间时，会出现一个死循环问题。  
例如：查找区间为\{4，6），要查找的数为5.  
中位数的选取就会恒为4，因为根据数组索引，（begin+end）/2=begin，即（0+1）/2=0。  
并且下一次的区间（medium，end）还是原来的区间。  
这样就陷入了死循环，gg。  
因此，如果我们中位数采用了这样的算法，在后续过程中我们要注意：

> （偶数+奇数）/2=偶数  
> 为了避免死循环，我们要在查找算法中，对于中位数小于查找值的情况，将子区间的选取调整为（medium+1，end）

## 具体实现 ##

public int find(int[] array,int begin,int end,int k){
        
            //注意可能会超出上限
            int medium=(begin+end)/2;
            //如果还要继续往下找
            if(begin<end) {
        
                if (array[medium] == k) {
        
                    return medium;
                } else if (array[medium] < k) {
        
                    //加一的原因很好理解，因为当只剩两个数时，medium必然是小的那个数，因为可能会就此循环。
                    return find(array, medium + 1, end, k);
                } else if (array[medium] > k) {
        
                    return find(array, begin, medium, k);
                }
            }else{
        
                if (array[medium] == k) {
        
                    return medium;
                }
            }
            //没能找到
            return -1;
        }