二分查找模板代码总结

2023-11-08 15:23:40

前言

二分查找作为程序员的一项基本技能，是面试官最常使用来考察程序员基本素质的算法之一，也是解决很多查找类题目的常用方法，它可以达到O(log n)的时间复杂度。

一般而言，当一个题目出现以下特性时，你就应该立即联想到它可能需要使用二分查找：

待查找的数组有序或者部分有序
要求时间复杂度低于O(n)，或者直接要求时间复杂度为O(log n)

二分查找有很多种变体，使用时需要注意查找条件，判断条件和左右边界的更新方式，三者配合不好就很容易出现死循环或者遗漏区域，本篇中我们将介绍常见的几种查找方式的模板代码，包括：

标准的二分查找
二分查找左边界
二分查找右边界
二分查找左右边界
二分查找极值点

标准二分查找

首先给出标准二分查找的模板：

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

循环条件： left <= right
中间位置计算： mid = left + ((right -left) >> 1)
左边界更新：left = mid + 1
右边界更新： right = mid - 1
返回值： mid / -1

这里有几点需要注意：

我们的循环条件中包含了 left == right的情况，则我们必须在每次循环中改变 left 和 right的指向，以防止进入死循环
循环终止的条件包括：
- 找到了目标值
- left > right （这种情况发生于当left, mid, right指向同一个数时，这个数还不是目标值，则整个查找结束。）
left + ((right -left) >> 1) 其实和 (left + right) / 2是等价的，这样写的目的一个是为了防止 (left + right)出现溢出，一个是用右移操作替代除法提升性能。
left + ((right -left) >> 1) 对于目标区域长度为奇数而言，是处于正中间的，对于长度为偶数而言，是中间偏左的。因此左右边界相遇时，只会是以下两种情况：
- left/mid , right (left, mid 指向同一个数，right指向它的下一个数)
- left/mid/right （left, mid, right 指向同一个数）

即因为mid对于长度为偶数的区间总是偏左的，所以当区间长度小于等于2时，mid 总是和 left在同一侧。

实战1：猜数字大小

leetcode 原题： https://leetcode.com/problems...
难度等级： Easy

猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num
返回我选出的数字。

示例 1：

输入：n = 10, pick = 6
输出：6

这题基本是可以直接照搬二分查找的，出题者没有做任何包装，我们直接使用标准二分查找：

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 1;
        int right = n;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (guess(mid) == 0) {
                return mid;
            } else if (guess(mid) == -1) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

实战2： x 的平方根

leetcode 原题： https://leetcode.com/problems...
难度等级： Easy

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

这一题其实是二分查找的应用，乍一看好像和二分查找没有关系，但是我们可以用二分查找的思想快速定位到目标值的平方根，属于二分查找的一个简单运用：

class Solution {
    public int mySqrt(int x) {
        if (x <= 1) return x;
        int left = 1;
        int right = x - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (mid > x / mid) {
                right = mid - 1;
            } else if (mid < x / mid) {
                if (mid + 1 > x / (mid + 1)) return mid;
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1; // only for return a value
    }
}

虽然是简单的题目，但是还是要注意对溢出的处理，例如我们使用 mid > x / mid 而不是 mid * mide > x 作为判断条件，因为后者可能会导致溢出，这与我们使用 left + ((right - left) >> 1) 而不是 (left + right) / 2 作为mid的值是一个道理，这是因为 left + right 也可能溢出。

二分查找左边界

利用二分法寻找左边界是二分查找的一个变体，应用它的题目常常有以下几种特性之一：

数组有序，但包含重复元素
数组部分有序，且不包含重复元素
数组部分有序，且包含重复元素

左边界查找类型1

类型1包括了上面说的第一种，第二种情况。

既然要寻找左边界，搜索范围就需要从右边开始，不断往左边收缩，也就是说即使我们找到了nums[mid] == target, 这个mid的位置也不一定就是最左侧的那个边界，我们还是要向左侧查找，所以我们在nums[mid]偏大或者nums[mid]就等于目标值的时候，继续收缩右边界，算法模板如下：

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

循环条件： left < right
中间位置计算： mid = left + ((right -left) >> 1)
左边界更新：left = mid + 1
右边界更新： right = mid
返回值： nums[left] == target ? left : -1

与标准的二分查找不同：

首先，这里的右边界的更新是right = mid，因为我们需要在找到目标值后，继续向左寻找左边界。

其次，这里的循环条件是left < right。
因为在最后left与right相邻的时候，mid和left处于相同的位置(前面说过，mid偏左)，则下一步，无论怎样，left, mid, right都将指向同一个位置，如果此时循环的条件是left <= right，则我们需要再进入一遍循环，此时，如果nums[mid] < target还好说，循环正常终止；否则，我们会令right = mid，这样并没有改变left,mid,right的位置，将进入死循环。

事实上，我们只需要遍历到left和right相邻的情况就行了，因为这一轮循环后，无论怎样，left,mid,right都会指向同一个位置，而如果这个位置的值等于目标值，则它就一定是最左侧的目标值；如果不等于目标值，则说明没有找到目标值，这也就是为什么返回值是nums[left] == target ? left : -1。

左边界查找类型2

左边界查找的第二种类型用于数组部分有序且包含重复元素的情况，这种条件下在我们向左收缩的时候，不能简单的令 right = mid，因为有重复元素的存在，这会导致我们有可能遗漏掉一部分区域，此时向左收缩只能采用比较保守的方式，代码模板如下：

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

它与类型1的唯一区别就在于对右侧值的收缩更加保守。这种收缩方式可以有效地防止我们一下子跳过了目标边界从而导致了搜索区域的遗漏。

关于这种类型的例子，可以看下面的实战5。

实战3：第一个错误的版本

leetcode 原题： https://leetcode.com/problems...
难度等级： Easy

这道题的题目比较长，原题就不贴了，大意就是说：有这么一个数组：

[false, false, false, ..., fasle, true, true, ..., true]

求最左侧的那个true的位置。

这就是一个典型的查找左边界的问题：数组中包含重复元素，我们需要找到最左侧边界的位置。直接使用二分查找左边界的模板就行了：

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 0;
        int right = n;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (!isBadVersion(mid)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return isBadVersion(left ) ? left : -1;
    }
}

与之类似的例子还有：LeetCode 744 等，都是Easy级别的题目，简单的使用二分查找左边界的模板就行了，大家可以自行练习。

当然，除了这种显而易见的题目，对于一些变体，我们也应该要有能力去分辨，比如说这一题：LeetCode 658 。

实战4：寻找旋转排序数组中的最小值

leetcode 原题： https://leetcode.com/problems...
难度等级： Medium

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值互不相同的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

这一题看上去没有重复元素，但是它也是查找左边界的一种形式，即可以看做是查找旋转到右侧的部分的左边界，有了这个思想，直接用二分查找左边界的模板就行了：

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

实战5：寻找旋转排序数组中的最小值 II

leetcode 原题： https://leetcode.com/problems...
难度等级： Hard

这道题目和上面的实战2类似，只是多了一个条件——数组中可能包含重复元素，这就是我们之前说的二分查找左边界的第二种类型，在这种情况下，我们只能采用保守收缩的方式，以规避重复元素带来的对于单调性的破坏：

class Solution {
    public int findMin(int[] nums) {
        if (nums.length == 1) return nums[0];
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] > nums[right]) { // mid 位于旋转点左侧
                left = mid + 1;
            } else if (nums[mid] < nums[right]) { // mid 位于旋转点右侧
                right = mid;
            } else { 
                // 注意相等的时候的特殊处理，因为要向左查找左边界，所以直接收缩右边界
                right--;
            }
        }
        return nums[left];
    }
}

二分查找右边界

有了寻找左边界的分析之后，再来看寻找右边界就容易很多了，毕竟左右两种情况是对称的，关于使用场景这里就不再赘述，直接给出模板代码：

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

循环条件： left < right
中间位置计算： mid = left + ((right -left) >> 1) + 1
左边界更新：left = mid
右边界更新： right = mid - 1
返回值： nums[right] == target ? right : -1

这里大部分和寻找左边界是对称着来写，唯独有一点需要尤其注意——中间位置的计算变了，我们在末尾多加了1。这样，无论对于奇数还是偶数，这个中间的位置都是偏右的。

对于这个操作的理解，从对称的角度看，寻找左边界的时候，中间位置是偏左的，那寻找右边界的时候，中间位置就应该偏右，但是这显然不是根本原因。根本原因是，在最后left和right相邻时，如果mid偏左，则left, mid指向同一个位置，right指向它们的下一个位置，在nums[left]已经等于目标值的情况下，这三个位置的值都不会更新，从而进入了死循环。所以我们应该让mid偏右，这样left就能向右移动。这也就是为什么我们之前一直强调查找条件，判断条件和左右边界的更新方式三者之间需要配合使用。

右边界的查找一般来说不会单独使用，如有需要，一般是需要同时查找左右边界。

二分查找左右边界

前面我们介绍了左边界和右边界的查找，那么查找左右边界就容易很多了——只要分别查找左边界和右边界就行了。

实战6: 在排序数组中查找元素的第一个和最后一个位置

leetcode 原题： https://leetcode.com/problems...
难度等级： Medium

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

这是一道特别标准的查找左右边界的题目，我们只需要分别查找左边界和右边界就行了：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = new int[]{-1,-1}; 
        if(nums == null || nums.length == 0){
            return ans;
        }
        int left = 0, right =  nums.length - 1;
        while(left < right){
            int mid = (right - left) / 2 + left;
            if(nums[mid] < target){
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        ans[0] = nums[left] == target? left: -1;
        if(ans[0] != -1){
            left = 0;
            right = nums.length - 1;
            while(left < right){
                int mid = (right - left) / 2 + left + 1;
                if(nums[mid] >target){
                    right = mid -1;
                }else{
                    left = mid;
                }
            }
            ans[1] = nums[right] == target? right: -1;
        }
        return ans;
    }
}

二分查找极值

二分查找还有一种有趣的变体是二分查找极值点，之前我们使用nums[mid]去比较的时候，常常是和给定的目标值target比，或者和左右边界比较，在二分查找极值点的应用中，我们是和相邻元素去比，以完成某种单调性的检测。关于这一点，我们直接来看一个例子就明白了。

实战7：寻找峰值

leetcode 原题：https://leetcode.com/problems...
难度等级： Medium

峰值元素是指其值大于左右相邻值的元素。

给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

这一题的有趣之处在于他要求求一个局部极大值点，并且整个数组不包含重复元素。所以整个数组甚至可以是无序的——你可能很难想象我们可以在一个无序的数组中直接使用二分查找，但是没错！我们确实可以这么干！

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

这里尤其注意我们的判断条件nums[mid] < nums[mid + 1]，这实际上是在判断处于mid处的相邻元素的单调性。

总结

除了本文所介绍的二分查找的应用方式，二分查找其实还有很多其他的变体和应用，但它们基本上是循环条件，判断条件，边界更新方法的不同组合，例如，有的二分查找的循环条件可以是 while(left + 1 < right)，有的边界的更新的条件需要依赖 nums[left], nums[mid], nums[mid+1], nums[right]四个值的相互关系。

但是无论如何，代码模板只是给大家一个理解问题的角度，生搬硬套总是不好的。实际应用中，我们只要记住循环条件，判断条件与边界更新方法三者之间的配套使用就行了，基于这一点原则，你就可以使用你自己习惯的方式来实现二分搜索。

但是，如果你真的只是想应付面试，我想下面这个表的总结应该就差不多足够用了：

查找方式	循环条件	左侧更新	右侧更新	中间点位置	返回值
标准二分查找	`left <= right`	`left = mid - 1`	`right = mid + 1`	`(left + right) / 2`	`-1 / mid`
二分找左边界	`left < right`	`left = mid - 1`	`right = mid`	`(left + right) / 2`	`-1 / left`
二分找右边界	`left < right`	`left = mid`	`right = mid - 1`	`(left + right) / 2 + 1`	`-1 / right`