您的位置: 首页 > 技术杂谈 > 正文

发现了二分查找的秘密

2022-11-11 12:00 https://my.oschina.net/jiagoushi/blog/5590959 博学谷狂野架构师次阅读条评论

NGINX Sprint China 2022--NGINX年度旗舰盛会，已开启免费预约！ >>>

**二分查找(Binary Search)**算法，也叫折半查找算法。

1.1、原理分析

二分查找是一种非常简单易懂的快速查找算法，其思想在生活中随处可见，比如朋友聚会的时候爱玩的一个猜数游戏，我随机写一个0-100之间的数字，然后大家依次来猜，猜的过程中大家每猜一次我都会告诉大家猜大了还是猜小了，直到有人猜中为止，猜中的人会有一些惩罚措施。这个过程其实就是二分查找思想的一种体现。

回到实际的开发场景中，假设有10个订单，其金额分别是：6，12，15，19，24，26，29，35，46，67。请从中找出订单金额为15的订单，利用二分查找的思想我们每次都与区间中间的数据进行大小的比较以缩小查找的范围，下面这幅图代表了查找的过程，其中 left，right代表了待查找区间的下标，mid表示待查找区间中间元素的下标(如果范围区间是偶数个导致中间数有两个就选择较小的那个)

file

通过这个查找过程我们可以对二分查找的思想做一个汇总：二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0

1.2、复杂度分析

理解了二分查找的思想后我们来分析二分查找的时间复杂度，首先我们要明确二分查找是一种非常高效的查找算法，通过分析其时间复杂度我们就可以发现，我们假设数据大小为n，每次查找完后数据的大小缩减为原来的一半，直到最后数据大小被缩减为1此时停止，如果我们用数据来描述其变化的规律那就是：

n，n/2，n/4，n/8，n/16，n/32，.......................，1；

可以看出来，这是一个等比数列，当数据大小变为1时：

其中k 的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较，所以，经过了 k 次区间缩小操作，通过计算k的值我们可以得出二分查找的时间复杂度就是 O(logn)

这是一种非常高效的时间复杂度，有时候甚至比O(1)复杂度更高效，为什么这么说呢？因为对于log n来说即使n非常的大对应的log n的值也会很小，之前在学习O(1)复杂度时我们讲过O(1)代表的是一种常量级复杂度并不是说代码只需要执行一次，有时候可能要执行100次，1000次这种常数级次数的复杂度都可以用O(1)表示，所以，常量级时间复杂度的算法有时候可能还没有 O(logn) 的算法执行效率高。

1.3、代码实现

二分查找的实现方式有基于循环的实现方式，也有基于递归的方式，现给出这两种方式编写的代码模板

1、基于循环的二分查找代码模板

// 返回的是元素在数组中的下标
public int binarySearch(int[] array, int target) {
        int left = 0, right = array.length - 1, mid;
        while (left <= right) {
            // mid = （left + right）>> 1
            mid  = left + ((right - left) >>1) ;

            if (array[mid] == target) {
                return mid;
            } else if (array[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return -1;
    }

用mid不断去逼近我们的目标值，相对好的情况直接在某段中间找到了目标值，最坏的情况是不断去逼近，最后left==right找到目标值，当然如果真的找不到目标值也就是left>right的时候。

2、基于递归的二分查找代码模板

public int recurBinarySearch(int[] array, int target,int left,int right) {
        //terminal
        if (left > right) {
            return -1;
        }
        //process current   计算中间元素的下标
        int mid = left + ((right - left)>>1);
        if (array[mid] == target) {
            return mid;
        }else if (array[mid] > target) {
            //drill down
            return recurBinarySearch(array,target,left,mid-1);
        }else {
            return recurBinarySearch(array,target,mid+1,right);
        }
    }

进阶：二分查找的实现我们可以分为两大类情况

1，有序数列中不存在重复元素的简单实现；

2：有序数列中存在重复元素的变形实现，

针对第一种，上面已经给出了代码模板，针对第二种，在实际的应用场景中可能会出现如下几种情况：

2.1、从数据序列中查找第一个值等于给定值的元素，比如在{6,12,15,19,24,26,29,29,29,67}中找第一个等于29的元素

2.2、从数据序列中查找最后一个值等于给定值的元素。还是刚刚的元素序列，找最后一个等于29的元素

2.3、从数据序列中查找第一个大于等于给定值的元素。

2.4、从数据序列中查找出最后一个值小于等于给定值的元素。

课后思考：针对这四种情况，代码应该如何实现呢？

1.4、应用场景说明

二分查找的时间复杂度是O(log n)，其效率非常高，那是不是说所有情况下都可以使用二分查找呢？下面我们讨论一下二分查找的应用前提

1、待查找的数据序列必须有序

二分查找对这一要求比较苛刻，待查找的数据序列必须是有序的（单调递增或者单调递减），假如数据无序，那我们要先排序，然后二分查找，如果我们针对的是一组固定的静态数据，也就说该数据序列不会进行插入和删除操作，那我们完全可以先排序然后二分查找，这样子一次排序多次查找；但是如果数据序列本身不是固定的静态的，可能涉及数据序列的插入和删除操作，那我们每次查找前都需要进行排序然后才能查找，这样子成本非常的高。

2、数据的存储依赖数组

待查找的数据序列需要使用数组进存储，也就是说依赖顺序存储结构。那难道不能用其他的结构来存储待查找的数据序列吗？比如使用链表来存储，答案是不可以的，通过我们前面实现的二分查找的过程可知，二分查找，算法需要根据下标，left,right,mid来访问数据序列中的元素，数组按照下标访问元素的复杂度是O(1)，而链表访问元素的时间复杂度是O(n)，因此如果使用链表来存储数据二分查找的时间复杂度就会变得很高。

3、数据序列存在上下边界

数据序列有上下边界，才能找到中间点，这样才能二分下去。

4、数据量太小或太大都不适合用二分查找

数据量很小的情况下，没有必要使用二分查找，使用循环遍历就够了，因为只有在数据量比较大的情况下二分查找才能体现出优势，不过在某些情况下即使数据量很小也建议大家使用二分查找，比如数据序列中的数据都是一些长度非常长的字符串，这些长度非常长的字符串比较起来也会非常的耗时，所以我们要尽可能的减少比较的次数，这样反倒有助于提高性能。

那为什么数据量太大的情况下也不建议使用二分查找呢？因为我们前面刚讲到二分查找底层需要依赖数组存储待查找的数据序列，而数组的特点是需要连续的内存空间，比如现在有1G的订单数据，如果用数组来存储就需要1G的连续内存，即便有2G的剩余内存空间，如果这2G的内存空间不连续那也无法申请到1G大小的数组空间，所以我们说数据量太大也不适合用二分查找。

2、面试实战

69. x 的平方根

字节跳动，美团点评最近面试题，69. x 的平方根

class Solution {
     // 求sqrt(x)即求：x=n^2 (n>0),就是我们所熟知的抛物线(y=x^2)右侧，单调递增,且有上下界,[1,x/2]
    public int mySqrt(int x) {
        //特殊判断
        if (x <=1) {
            return x;
        }
        //找一个数k,k^2<=x,找一个最大的k就是我们想要的
        long left=1,right = x>>1,mid = 0;
        while (left <=right ) {
            mid = (left+right) >>1;
            if (mid * mid  < x) {
                left = mid + 1;
            }else if (mid * mid > x) {
                right = mid - 1;
            }else {
                return (int)mid;
            }
        }
        return (int)left-1;
    }
}

代码解释：

1：如果正好找到一个mid^2 = x则在while loop中就可以直接返回了，

2：如果while loop中还没找到，就类似x=8，我们在[ 1，2，3，4 ]中去寻找，while loop中最后一次循环left == right == 3，我们只需找k^2 <=x的最大k值即可。

进阶：牛顿迭代法解决该问题！参考精选题解：https://leetcode-cn.com/problems/sqrtx/solution/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/方法二

同类题目：367. 有效的完全平方数

class Solution {
    public boolean isPerfectSquare(int x) {
        //特殊判断
        if (x <=1) {
            return true;
        }
        long left=1,right = x>>1,mid = 0;
        while (left <=right ) {
            mid = (left+right) >>1;
            if (mid * mid  < x) {
                left = mid + 1;
            }else if (mid * mid > x) {
                right = mid - 1;
            }else {
                return true;
            }
        }
        return false;
    }
}

33. 搜索旋转排序数组

字节，快手，百度最近面试题，33. 搜索旋转排序数组

二分查找的变形题目

思考要点：

1：二分的条件：满足有上下边界，数组存储可利用下标获取，单调性这块原始数组是单调递增的，旋转之后虽然整体不是单调性的，但是其中有一半一定是单调递增的。

2：要达到log n的复杂度肯定是要二分，但是并不能简单套用二分的模板，我们需要先找到哪半部分是具备单调性的，并判断target是否在该范围内，如果在则在这部分查找target，如果不在则在另外半部分查找。

class Solution {
    public int search(int[] nums, int target) {
        //此处left，right代表的是下标
        int left=0,right = nums.length-1,mid=0;
        while (left <= right) {
            mid = (left+right) >>1;

            if (nums[mid] == target) {
                return mid;
            }

            //前半部分有序
            if (nums[left] <= nums[mid]) {
                //target如果在前半部分则在前半部分找,否则在后半部分找
                if (target < nums[mid] && target >=nums[left] ) {
                    right = mid -1;
                }else {
                    left = mid + 1;
                }
            }else {
                //后半部分有序
                //target如果在后半部分则在后半部分找，否则在前半部分找
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid +1;
                }else {
                    right = mid -1;
                }
            }

        }
        return -1;

    }
}

153. 寻找旋转排序数组中的最小值

网易，拼多多，今日头条面试题，153. 寻找旋转排序数组中的最小值

class Solution {
    //二分,但不能套用简单的二分模板,修改二分的判断条件
    public int findMin(int[] nums) {
        int left=0,right=nums.length-1,mid = 0;

        /*
            在这里如果left==right则可以直接返回了,最小元素一定是它
        */
        while (left < right ) {

            mid = (left + right) >>1;
            
            if (nums[mid] < nums[right]) {//右区间连续,最小值一定在左半区间
                //mid可能是最小值也可能不是，简单二分的模板代码写right=mid-1;
                right = mid;
            }else if (nums[mid] > nums[right]) { //右边区间不连续,最小值一定在该区间内
                left = mid +1;
            }
        }
        return nums[left];

    }
}

进阶思考题：

使用二分查找，寻找一个半有序数组 [4, 5, 6, 7, 0, 1, 2] 中间无序的地方

74. 搜索二维矩阵

新浪，爱奇艺，三星面试题，74. 搜索二维矩阵

解题思路：标准的二分m x n的矩阵可以看成 m x n 的有序数组

参考官方题解：https://leetcode-cn.com/problems/search-a-2d-matrix/solution/sou-suo-er-wei-ju-zhen-by-leetcode/

class Solution {
    //标准的二分m x n的矩阵可以看成 m x n 的有序数组
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if (m ==0) {
            return false;
        }
        int n = matrix[0].length;
        int left = 0;
        int right = m * n  -1;

        int mid=0,row=0,col=0;

        while (left<=right) {
            mid = (left+right)>>1;
            //最重要的就是将mid转换陈二维数组中的下标。
            row = mid / n;
            col = mid % n;

            if (matrix[row][col] == target) {
                return true;
            }else if (matrix[row][col] < target) {
                left = mid +1;
            }else {
                right = mid-1;
            }
        }
        return false;
    }
}