简单的自我介绍

我是一名双非大二学生，目前学习方向为Java后端，快速学习并学到了springboot，并和实验室的朋友做了一个简单的微信小程序，想在寒假找份有关互联网的实习，打算海投，城市和公司暂时没有特别强烈的意向，我会再次牢固的复习一遍Java整套学习知识，并且开始补充算法知识刷算法题，来备战这次寒假实习，并且想报名参加蓝桥杯Java B组的比赛，希望我的一些学习笔记能为你带来一些帮助，这次给大家带来的是折半算法也就是算法中用的很多的二分查找，学习这个来应对蓝桥杯和某些公司实习的算法笔试。

折半查找是什么？

折半查找又叫二分查找，是查找算法的一种，在顺序情况下有着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算法】前面公布，如果本篇文章对大家有帮助，可以点个赞，感谢~！