二分查找

二分查找是一种很常见的思想,在我们玩猜数字的游戏时,要是猜0-100的某一个数字,假设是84,我们首先就会猜50,发现小了,就会猜75,要是还是 小了,就会猜85,发现大了 就会猜80,接着就是82,然后就是84,这样就能才对,这里的猜数字就用到了二分的思想,每次都能 去掉一半的错误数字,要是数据量更加大,二分的思想就会更有效率.

基本的二分查找方法

给定一个有序的数组,要求找出数组中的某一个数字,要是找到就返回下标,要想找不到就返回-1

通过二分的思想,我们可以先定义左右两个下标 来不断逼近要寻找的数字

public static int BinarySearch(int[] arr, int num) {
    int left = 0;
    int right = arr.length-1;
    while (left <= right) { //注意循环结束条件
        int  mid = left + ((right - left )>>1);
        if (arr[mid] > num) {
                right = mid -1;
        } else if (arr[mid] < num) {
            left = mid + 1;
        }else{
            return mid;
        }
    }
    return -1;
}

在定义mid的时候,要是写成 int mid = (right + left )/2;如果左右下标很大,就会造成越界,可以这样定义mid

int mid = left + (right - left )/2; 要是还要想要更有效率,就能使用位运算int mid = left + ((right - left )>>1); 加号的优先级大于>>,所以一定也要加上 括号

二分查找的递归写法

public  static  int BinarySearch2(int[] arr ,int num ){
    return binary(arr,0, arr.length-1, num);
}

public static int binary(int[] arr,int left, int right, int num ) {
    if (left > right) {
        return -1;
    }
    int mid = left + ((right - left) >> 1);
    if (arr[mid] > num) {
       return  binary(arr, 0, mid - 1, num);
    } else if (arr[mid] < num) {
       return  binary(arr, mid + 1, arr.length, num);
    }else{
        return mid;
    }
}

二分查找的时间复杂度

在知道了二分查找的具体实现代码之后,我们再来想一想二分查找的时间复杂度

二分查找每次都会减少一半的数字,所以就是 n n/2 n/2^2 n/2^3 ...... n/2^k ,最坏的情况就是最后只剩一个数字,此时n/2^k =1;

所以次数k就是logn,所以二分查找的时间复杂度就是O(logn)

一定要知道二分查找的前提是有序数组,要是无序,要先进行排序

以上就是二分查找的一些最基本的要点,接下来会一些关于二分查找的变式,会十分的有趣

以下的所有的变式都有一个大前提: 数组是有序的,且 是从小到大的顺序

变式一:查找第一个值等于num的元素

给定一组有序数组,里面可能会有重复的数字,要求找到第一次出现的数字的下标

eg: 有一组数组 1 4 5 5 5 8,现在我要寻找5 ,那么程序就要返回第一次出现5的下标 ,也就是2

思路 : 当arr[mid] > num的时候,还是right = mid -1;当 arr[mid] < num 的时候,还是 left = mid +1;

当arr[mid] == num时,需要确认一下此时的mid是不是第一个值,要是此时mid已经是数组的首项了,那一定是第一个值,或者 arr[mid] 前面的数字不是num ,也就能说明 此时,arr[mid] 就是第一个值,以上两种情况都不是,就只能说明前面还有相同的值,此时right 就还要向前去找

public static int Binary1(int[] arr,int num ) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = left + ((right - left)>>1);
        if (arr[mid] > num) {
            right = mid -1;
        }else if(arr[mid] < num){
            left = mid+1;
        }else{
            if (mid == 0 || arr[mid - 1] != num) {  //顺序不能变, 只有不在首项,才能使用arr[mid-1] 
                return mid;
            }else{
                right  = mid -1;
            }
        }
    }
    return -1;
}

变式二:查找最后一个值等于num的元素

eg: 有一组数组 1 4 5 5 5 8,现在我要寻找5 ,那么程序就要返回最后一次出现5的下标 ,也就是4

思路 : 当arr[mid] 大于或者 小于num时,还是一样的进行移动,当arr[mid] 等于 num 时 ,由于要找的是最后一个值 ,所以要是此时的arr[mid]就是最后一个值,或者 后面的值不等于num的话,就能说明此时mid就是最后一个值的下标

public static int Binary2(int[] arr,int num) { 
    int left = 0;
    int right = arr.length-1;
    while (left <= right) {
        int mid = left + ((right - left )>>1);
        if(arr[mid] > num ) {
            right = mid - 1;
        } else if (arr[mid] < num) {
            left = mid + 1;
        }else{
            if(mid == arr.length-1 || arr[mid + 1] != num ){
                return mid;
            }else{
                left = mid +1;
            }
        }
    }
    return -1;
}

变式三: 查找第一个大于等于给定值的元素

eg: 有一组数组 1 3 5 8,现在我要寻找4 ,那么程序就要返回第一次大于等于4的元素的下标,也就是5下标2

当arr[mid] > = num时,此时就要判断,要是此时mid ==0 (在数组的首项) 或者 arr[mid] 前一个 数字小于 num,这都能说明此时arr[mid]

就是第一个大于等于给定值 的元素,要是不满足的话,说明此时前面还有,此时就让right向前找, right = mid -1;

public static int Binary3(int[] arr , int num ) {
    int left = 0;
    int right = arr.length-1;
    while (left <= right) {
        int mid = left + ((right -left)>>1);
        if (arr[mid] < num) {
            left = mid + 1;
        }else{
            if(mid == 0 || arr[mid -1] < num){
                return mid;
            }else{
                right = mid -1;
            }
        }
    }
    return -1;
}

变式四: 查找最后一个小于等于给定值的元素

eg: 有一组数组 1 3 5 8,现在我要寻找9 ,那么程序就要返回最后一个小于等于9的元素的下标,也就是8的下标3

与上面的思路是一样的,

public static int Binary4(int[] arr, int num) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right){
        int mid = left + ((right - left) >> 1);
        if(arr[mid] > num){
            right = mid -1;
        }else{
            if(mid == arr.length-1 || arr[mid + 1] > num){
                return  mid;
            }else{
                left = mid +1;//说明此时后面还有 小于等于给定值的数字,所以还要让left向后找
            }
        }
    }
    return -1;
}