【面试：基础篇01：整数二分查找】

01.简介

二分查找是查找算法的一种，在顺序情况下有着 $\log_2^N$良好的时间复杂度

02.算法步骤

在{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

可以看出我们总共查找了四次就查出了结果

03.算法实现

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;
    }

结果

l:0 r:10
l:6 r:10
l:6 r:7
l:7 r:7
7

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

04.优化mid溢出问题

问题介绍：

当我们mid=(l+r)/2时 l+r如果数值过于大就会溢出

例子

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太大溢出
    }

结果

-536870913，可以看出此时mid已经溢出

解决方法1

public static void Overflow1(){// 整数溢出问题
    int l=0,r=Integer.MAX_VALUE-1;
    int mid = (l+r)/2;
    l=mid+1;
    mid = (l+r)/2;
    System.out.println(mid);// mid太大溢出
    //此时我们变化形式
    mid = l+(r-l)/2;
    System.out.println(mid);// 可以看出此时没有溢出
}

结果

-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);
}

结果

1073741823
1610612735

可以看出此时也没有溢出

方法2 采用的是位运算中的右移运算¹，是最推荐的写法，速度快，结果准

05.面试题

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个元素的数组中二分查找一个数，需要比较的次数最多不超过多少次

第一题：

可以看出这和我最开始举得例子基本一致

第一次 我们的l=0 r=12，所以mid=(l+r)/2=6 ，此时mid下标对应的元素是31小于48 所以我们令l=mid+1

第二次 我们的l=7 r=12，所以mid=(l+r)/2=9，此时mid下标对应的元素是45小于48 所以我们令l=mid+1

第三次我们的l=10 r=12，所以mid=(l+r)/2=11，此时mid下标对应的元素是49大于48 所以我们令r=mid-1

第四次我们的l=10 r=10，所以mid=(l+r)/2=10，此时mid下标对应的元素是48 即我们需要的元素

自此我们找到元素48共经过四次比较

第二题与第一题基本一样 所以不在赘述

第三题：

因为二分查找的时间复杂度是$log_2^N$ ，所以此题的答案就是$log_2 128$ 等于7

注意：如果 $log_2^N$ 的结果不是整数 则向下取整+1