今天会是有Offer的一天么：面试时你真的会写二分查找么

二分查找是一种非常常见的算法，在面试时会经常被问到。其输入是一个有序的数组，输出需要查找数字的下标（注意输入一定是有序的）。

先说一下最基本的，有序数组中没有重复的元素。

public  class  binarySearchTest {
    public static void main(String[] args) {
        int[]num=new int[]{1,4,6,7,9,10,14,18,19,27,30};///初始数组一定是有序的
        int key=27;
        System.out.println("初始数组为：");
        for(int i=0;i<num.length;i++){
            System.out.print(num[i]+" ");
        }
        System.out.println();
        System.out.println("要查找的数字："+key);
        binarySearch(num,key);
    }
public static int binarySearch(int[]num,int key)
{
    int left=0;
    int right=num.length-1;
    ///这里一定要注意是left<=right
    while(left<=right){
        int middle=(left+right)/2;
        System.out.println("left="+num[left]+"  right="+num[right]+"   middle="+num[middle]);
        if (num[middle] == key) {
            System.out.println("查找成功");
            return middle;
        }else if(num[middle]<key){
            left=middle+1;
        }else{
            right=middle-1;
        }
    }
    System.out.println("查找失败");
    return -1;
}

}

接着说一下二分查找的变种，比如说对于一个有序数组中，可以存在重复的元素。

查找第一个与key相同的数字的下标

public  class  binarySearchTest {
    public static void main(String[] args) {
        int[]num=new int[]{1,4,4,4,6,7,9,10,14,18,19,27,30};///初始数组一定是有序的
        int key=4;
        System.out.println("初始数组为：");
        for(int i=0;i<num.length;i++){
            System.out.print(num[i]+" ");
        }
        System.out.println();
        System.out.println("要查找的数字："+key);
        binarySearch(num,key);
    }
public static int binarySearch(int[]num,int key)
{
    int left=0;
    int right=num.length-1;
    ///这里一定要注意是left<=right
    while(left<=right){
        int middle=(left+right)/2;
        System.out.println("left="+num[left]+"  right="+num[right]+"   middle="+num[middle]);
        if(num[middle]>=key){
            right=middle-1;
        }else{
            left=middle+1;
        }
    }
     System.out.println("最后一次查询： "+"left="+num[left]+"  right="+num[right]);
    //这里需要判断一下num[left]是否等于key
    if(left<num.length&&num[left]==key){
        System.out.println("查找成功");
        return left;
    }
    System.out.println("查找失败");
    return -1;
}

}

查找最后一个与key相等数字的下标

public  class  binarySearchTest {
    public static void main(String[] args) {
        int[]num=new int[]{1,4,6,7,9,10,10,10,10,14,18,19,27,30};///初始数组一定是有序的
        int key=10;
        System.out.println("初始数组为：");
        for(int i=0;i<num.length;i++){
            System.out.print(num[i]+" ");
        }
        System.out.println();
        System.out.println("要查找的数字："+key);
        binarySearch(num,key);
    }
public static int binarySearch(int[]num,int key)
{
    int left=0;
    int right=num.length-1;
    ///这里一定要注意是left<=right
    while(left<=right){
        int middle=(left+right)/2;
        System.out.println("left="+num[left]+"  right="+num[right]+"   middle="+num[middle]);
        if(num[middle]>key){
            right=middle-1;
        }else{
            left=middle+1;
        }
    }
    System.out.println("最后一次查询： "+"left="+num[left]+"  right="+num[right]);
    //这里需要判断一下num[left]是否等于key
    if(right>=0&&num[right]==key){
        System.out.println("查找成功");
        return right;
    }
    System.out.println("查找失败");
    return -1;
}

}

咱们接着说一下另外几种变种

查找第一个大于key的数字的下标

public  class  binarySearchTest {
    public static void main(String[] args) {
        int[]num=new int[]{1,4,4,4,6,7,9,10,14,18,19,27,30};///初始数组一定是有序的
        int key=4;
        System.out.println("初始数组为：");
        for(int i=0;i<num.length;i++){
            System.out.print(num[i]+" ");
        }
        System.out.println();
        System.out.println("要查找第一个大于："+key+"的数字");
        binarySearch(num,key);
    }
    public static int binarySearch(int[]num,int key)
    {
        int left=0;
        int right=num.length-1;
        ///这里一定要注意是left<=right
        while(left<=right){
            int middle=(left+right)/2;
            System.out.println("left="+num[left]+"  right="+num[right]+"   middle="+num[middle]);
            if(num[middle]>key){
                right=middle-1;
            }else{
                left=middle+1;
            }
        }
        System.out.println("最后一次查询： "+"left="+num[left]+"  right="+num[right]);
        //这里需要判断一下left是否小于num.length
        if(left<num.length){
            System.out.println("查找成功");
            return left;
        }
        System.out.println("查找失败");
        return -1;
    }

}

查找最后一个小于key的数字的下标

public  class  binarySearchTest {
    public static void main(String[] args) {
        int[]num=new int[]{1,4,4,4,6,7,9,10,14,18,19,27,30};///初始数组一定是有序的
        int key=18;
        System.out.println("初始数组为：");
        for(int i=0;i<num.length;i++){
            System.out.print(num[i]+" ");
        }
        System.out.println();
        System.out.println("要查找最后一个小于："+key+"的数字");
        binarySearch(num,key);
    }
    public static int binarySearch(int[]num,int key)
    {
        int left=0;
        int right=num.length-1;
        ///这里一定要注意是left<=right
        while(left<=right){
            int middle=(left+right)/2;
            System.out.println("left="+num[left]+"  right="+num[right]+"   middle="+num[middle]);
            if(num[middle]>=key){
                right=middle-1;
            }else{
                left=middle+1;
            }
        }
        System.out.println("最后一次查询： "+"left="+num[left]+"  right="+num[right]);
        //这里需要判断一下right是否大于等于0
        if(right>=0){
            System.out.println("查找成功");
            return right;
        }
        System.out.println("查找失败");
        return -1;
    }

}

最后两种变种

查找第一个等于或者大于key数字的下标

public  class  binarySearchTest {
    public static void main(String[] args) {
        int[]num=new int[]{1,4,4,4,6,7,9,10,14,18,19,27,30};///初始数组一定是有序的
        int key=8;
        System.out.println("初始数组为：");
        for(int i=0;i<num.length;i++){
            System.out.print(num[i]+" ");
        }
        System.out.println();
        System.out.println("要查找第一个等于或者大于："+key+"的数字");
        binarySearch(num,key);
    }
    public static int binarySearch(int[]num,int key)
    {
        int left=0;
        int right=num.length-1;
        ///这里一定要注意是left<=right
        while(left<=right){
            int middle=(left+right)/2;
            System.out.println("left="+num[left]+"  right="+num[right]+"   middle="+num[middle]);
            if(num[middle]>=key){
                right=middle-1;
            }else{
                left=middle+1;
            }
        }
        System.out.println("最后一次查询： "+"left="+num[left]+"  right="+num[right]);
        //这里需要判断一下
        if(left<=num.length){
            System.out.println("查找成功");
            return left;
        }
        System.out.println("查找失败");
        return -1;
    }

}

查找最后一个小于或等于key数字的下标

public  class  binarySearchTest {
    public static void main(String[] args) {
        int[]num=new int[]{1,4,4,4,6,7,9,10,14,18,19,27,30};///初始数组一定是有序的
        int key=8;
        System.out.println("初始数组为：");
        for(int i=0;i<num.length;i++){
            System.out.print(num[i]+" ");
        }
        System.out.println();
        System.out.println("要查找最后一个小于或等于："+key+"的数字");
        binarySearch(num,key);
    }
    public static int binarySearch(int[]num,int key)
    {
        int left=0;
        int right=num.length-1;
        ///这里一定要注意是left<=right
        while(left<=right){
            int middle=(left+right)/2;
            System.out.println("left="+num[left]+"  right="+num[right]+"   middle="+num[middle]);
            if(num[middle]>key){
                right=middle-1;
            }else{
                left=middle+1;
            }
        }
        System.out.println("最后一次查询： "+"left="+num[left]+"  right="+num[right]);
        //这里需要判断一下
        if(right>=0){
            System.out.println("查找成功");
            return right;
        }
        System.out.println("查找失败");
        return -1;
    }

}

二分查找的变化还是被较多的，但原理基本上都一样。掌握最基本的一种后，对于其他的，再写的时候要好好想一下他们的判断条件和边界。总之二分查找是我们最因该掌握的一种查找算法。