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

前言

二分查找是一种常用的查找算法，其优点在于查找速度较快，最优时间复杂度为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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21