折半查找是什么？

折半查找又叫二分查找，是查找算法的一种，在顺序情况下有着 log2N 非常棒的时间复杂度

算法原理

在{1,3,5,6,7,9,13,25,34,61,88} 总共 11 个元素中 找到 25 的步骤，规定下标从 0 开始

1. 首先我们选择下标 0,10 作为左右边界 l,r 中间值 mid=(l+r)/2，注意：这里的 l+r 均为整数 除 2 的结果若为小数向下取整

2. 此时我们的 mid=5，即元素 9 不等于 25，然后我们令 l=mid+1，注意：这里是 mid+1 而不是 mid 因为我们已经确定 mid 这个下标所对应的元素不等于 25 所以我们之间从 mid+1 开始找就行

3. 此时我们的 l=6 r=10，mid=(l+r)/2=8 即元素 34，此时 34 大于 25，我们令 r=mid-1

4. 此时我们的 l=6 r=7，mid=(l+r)/2=6 即元素 13 令 l=mid+1

5. 此时我们的 l=7 r=7，mid=(l+r)/2=7 即元素 25 找到了元素 25 此时返回对应下标 7 可以看出我们总共查找了四次就查出了结果

代码示例

public static void main(String[] args) {        int[] a = {1,3,5,6,7,9,13,25,34,61,88};        int res= 25;        int result = Search(a,res);        System.out.println(result);    }
    private static int Search(int[] a,int res) {        int l=0,r=a.length-1;        while (l<=r){            System.out.println("l:"+l+" r:"+r);            int mid = (l+r)/2;            if (a[mid]<res){                l=mid+1;            }else if (a[mid]>res){                r=mid-1;            }else{                return mid;            }        }        return -1;    }

PS：a 是已经排完序的数组，res 的值是我们要在数组中查找具体的一个值

最后输出情况 l:0 r:10

l:6 r:10

l:6 r:7

l:7 r:7

7

可以看出和我们的推理一样 查询了四次 最终的结果下标为 7

对算法进行更好的优化情况 1

public static void Overflow(){        int l=0,r=Integer.MAX_VALUE-1;        int mid = (l+r)/2;        System.out.println(mid);        l=mid+1;        mid = (l+r)/2;        System.out.println(mid);    }

这里对 mid 可能数值过大存不进去，出现错误值的情况进行优化，这个情况会出现在当我们 mid=(l+r)/2 时 l+r 如果数值过于大就会溢出

通过输出的结果可以看出来：-536870913 // 溢出时的结果

1610612735 // 变换形式后的结果

可以看出此时阻止了溢出

对算法进行更好的优化情况 2

private static void Overflow2() {    int l=0,r=Integer.MAX_VALUE-1;    int mid = (l+r)>>>1;    System.out.println(mid);    l=mid+1;    mid = (l+r)>>>1;    System.out.println(mid);}

通过对 mid 采用位运算 右移一位避免移除情况

结果：1073741823

1610612735

可以看出此时也没有溢出 PS：优化情况 2 是最推荐的算法写法，速度快，结果准

具体题目测试

1. 有一个有序表 1,5,8,11,19,22,31,35,40,45,48,49,50 当二分查找 48 时 查找成功需要比较的次数是?

2. 使用二分查找在序列 1,4,6,7,15,33,39,50,64,75,78,81,89,96 当二分查找 81 时 需要经过几次比较?

3. 在拥有 128 个元素的数组中二分查找一个数，需要比较的次数最多不超过多少次?

答案在下一期的【从 0 到 1 算法】前面公布，如果本篇文章对大家有帮助，可以点个赞，感谢~！