当前位置：首页 > article >正文

优选算法的匠心之艺：二分查找专题(一)

article 2025/3/15 7:30:10

专栏：算法的魔法世界

个人主页：手握风云

一、二分查找算法

二、例题讲解

2.1. 二分查找

2.2. 在排序数组中查找元素的第一个和最后一个位置

2.3. x 的平方根

2.4. 搜索插入位置

一、二分查找算法

可能很多老铁在之前可能接触过朴素的二分查找思想，比如在一个有序数组中找到目标值。但二分查找算法不仅仅局限于数组有序的场景下，只要一个数组里面符合“二段性”，当数组中间的某一个值不符合要求，我们就可以把这个值左区间或者右区间舍去，再去另一个区间进行查找。这个“二段性”，并不一定从中间划分，也可以1/3、1/4出开始划分。但我们大部分还是选择从中间划分，因为从概率学角度讲，中间划分是数学期望最高的。二分查找算法细节特别多，也特别容易写出死循环。但我们要理解了算法原理和二分查找的模板，那么就非常简单了。

二、例题讲解

2.1. 二分查找

对于上面的题，我们可以先使用暴力解法，利用for循环遍历数组中的每一个元素来找到目标值，这个算法的时间复杂度为 $O(n)=n$ 。

class Solution {
    public int search(int[] nums, int target) {
        for(int i = 0;i < nums.length;i++){
            if(nums[i] == target){
                return i;
            }
        }
        return -1;
    }
}

接下来对这个算法进行优化，我们先设x = (right + left)/2。如果nums[x] > target，那么left = x+1；如果nums[x] < target，那么right = x-1；如果nums[x] = target，直接返回x，循环走下来找不到，返回-1。

有些细节我们需要注意一下：1.循环结束的条件是什么？当x与目标值进行比较时，left可以移动到x右边，那么x的左边已经判断过了都是小于目标值，但右边还是未知的，即使left与right相遇，那这个数依然是未知的。所以循环结束的条件是left>right，而不是left==right。2.为什么二分查找是正确的？二分查找虽然不像上面的暴力解法一个一个比较，但我们利用“二段性”以及数组的有序性，只比较一个数字就排除一半的区间。3.二分查找的时间复杂度。当我们的循环执行一次时，将区间划分为 $\frac{n}{2}$ ；循环执行两次时将区间划分为 $\frac{n}{4}$ ；循环执行三次时将区间划分为 $\frac{n}{8}$ ……最坏情况下left与right相遇，将区间划分为1，则 $\frac{n}{2^{x}}=1$ ，时间复杂度为 $O(n)=logn$ 。

完整代码实现：

class Solution {
    public int search(int[] nums, int target) {
        int left = 0,right = nums.length-1;
        while(left <= right){
            int mid = (left + right)/2;
            if(nums[mid] > target) right = mid -1;
            else if(nums[mid] < target) left = mid +1;
            else return mid;
        }
        return -1;
    }
}

        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[……) 
                right = mid -1;
            else if(……) 
                left = mid +1;
            else 
                return mid;
        }

2.2. 在排序数组中查找元素的第一个和最后一个位置

我们的暴力解法，就是去从前往后遍历数组，找出起始位置用begin记录，然后找出结束位置用end记录，最终返回[begin,end]。很明显，暴力解法的时间复杂度为 $O(n) =n$ 。

我们还是根据数组有序的特性，来利用二分查找进行优化。这里我们不能使用上面的朴素二分查找，因为找出的中间值无法确定是不是起始位置或者结束位置，我们向左和向右遍历数组找出起始与结束，所以时间复杂度依然是 $O(n) =n$ 。所以朴素的二分查找不能解决问题。

我们还是要回归到二分查找的本质，“二段性”。我们先来查找区间的左端点，我们假设中间下标mid对应值的值为x，让x与target进行比较。如果x小于target，说明mid位于左边的区间，让left = mid+1；如果x大于等于target（这里等于的时候，并不一定是最终位置），说明mid位于右边的区间，让right=mid（因为mid指向的位置有可能正好是左区间）。

我们需要处理一下细节：1.循环条件。right指针移动的时候，一直是在合法的区间，left一直想要跳出这个不合法的区间，直到两个指针相遇，无需判断，相遇的位置就是我们要找的结果。并且如果left=right，一直处于x>=t的条件，而right指针又不会移动，就会陷入死循环。

2.找出中点操作。中点有两种求法，mid=left+(right-left)/2或者是mid=left+(right-left+1)/2。如果数组元素个数为偶数个，按照第二种求法，mid就会落在右边，又会陷入死循环，所以我们需要选择第一种求法。

接下来是查找区间的右端点，与上面的查找左端点的方法大同小异，只是细节的处理不一样。我们要划分的区间为小于等于target与大于tareget两部分，求中点的方式要采用第二种，防止mid落在左边的元素造成死循环。

完整代码实现：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[2];
        ret[0] = ret[1] = -1;

        //处理边界情况
        if (nums.length == 0) return ret;

        //查找左端点
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        //判断是否有结果
        if (nums[left] != target) return ret;
        else ret[0] = right;

        //二分右端点
        left = 0;
        right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        ret[1] = left;
        return ret;
    }
}

模板总结：

//查找左端点
while (left < right) {
    int mid = left + (right - left) / 2;
    if (……) left = mid + 1;
    else right = mid;
}

//查找右端点
while (left < right) {
    int mid = left + (right - left + 1) / 2;
    if (……) left = mid;
    else right = mid - 1;
}

2.3. x 的平方根

题目要求不适用内置函数求平方根，我们需要自己写一个算法来求平方根。如果求出的平方根是小数，则舍去小数部分。

我们先来思考暴力解法：由于x是非负整数，那么x的平方根定义是小于等于x的。其中0和1的平方根都为它本身。如果x=17，我们可以从1开始向右枚举，如果找到一个数n，n*n小于等于x，且(n+1)*(n+1)大于x，则x的平方根则为n。

我们可以直接套用上面的模板。如果mid * mid <= x，则left=mid；如果mid * mid > x，则right=mid+1。这里还有一点需要注意，mid*mid可能会因为数据太大造成溢出，所以mid用long来创建。

完整代码实现：

class Solution {
    public int mySqrt(int x) {
        if(x == 0) return 0;
        long left = 1,right = x;
        while(left < right){
            long mid = left + (right-left+1)/2;
            if(mid * mid <= x) left = mid;
            else right = mid-1;
        }
        return (int)left;
    }
}

2.4. 搜索插入位置

通过上面的示例分析，插入结果分为两种：1.插入第一个大于等于target前的位置；2.插入数组的末尾。很明显，我们可以按照查找区间左端点的模板来解决。我们还需要判断一下示例3这种情况，也就是插入数组的末尾。

完整代码实现：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0,right = nums.length-1;
        while(left < right){
            int mid = left + (right - left)/2;
            if(nums[mid] < target) left = mid+1;
            else right = mid;
        }
        if(nums[left] < target) return left+1;
        return left;
    }
}

查看全文

http://www.kler.cn/a/585233.html