二分查找算法

1. 讲解

是什么？

二分查找是一种基于分治策略（更准确地说是减治策略）的搜索算法。它通过将搜索区间不断对半分割，将搜索空间缩小为原来的一半，直到找到目标元素或搜索区间为空。

二分查找的本质并非“数组有序”，而是“二段性”。

要求数据支持随机访问：通常基于数组（可以通过下标 O(1) 时间访问元素），不适合链表。

什么时候用？

利用二段性：当发现一个规律，并根据这个规律选取某一个点后，能把数组分成两个部分，然后能根据规律有选择性地舍弃一部分，进而到另一部分中继续查找，就可以使用二分算法。

怎么用？

二分查找的模板主要分为三种，细节主要集中在循环条件和求中点的方式上

模板

1. 朴素二分：适用于在数组中查找某个具体值是否存在

while (left <= right) { // 特别注意这里是有等号的
     int mid = left + (right – left) / 2; // 防溢出
     if (……) {
         left = mid + 1;
    } else if (……) {
         right = mid – 1;
    } else {
         return ……;
    }
 }

• 细节1：循环条件。为什么是 left <= right？因为当区间缩小到一个点时（left == right），这个数还是未知的，需要放入循环里进行一次判断。

• 细节2：求中点。奇数个元素时，left + (right – left) / 2 和 left + (right – left + 1) / 2 指向的位置相同；偶数个元素时， 指向的位置不同。在朴素二分中，只要找到能将它划分开的点就行，偏左偏右没有影响。

2. 查找左边界的二分

当数组中有重复元素，或者需要寻找满足某条件的第一个位置时使用

while (left < right) { // 注意这里没有等号
     int mid = left + (right – left) / 2; // 偏左中点
     if (……) {
         left = mid + 1;
    } else {
         right = mid;
    }
 }

• 循环条件：left < right。当 left == right 的时候，就是最终结果，无需继续判断。如果用 <=，会造成死循环。（因为left == right 时，满足 right == mid ，会触发 else 分支，但出发后 right 的值没有变，就会一直陷入死循环）

• 求中点：使用 left + (right – left) / 2（偏左），配合 else right = mid 避免死循环。

• 口诀：让下面出现 -1 的时候（如 right = mid – 1），上面就加 +1。此处 else 是 right = mid，没有减1，所以上面 left = mid + 1。

3. 查找右边界的二分：当数组中有重复元素，或者需要寻找满足某条件的最后一个位置时使用

while (left < right) { // 注意这里没有等号
     int mid = left + (right – left + 1) / 2; // 偏右中点，防死循环
     if (……) {
         left = mid;
    } else {
         right = mid – 1;
    }
 }

• 循环条件：：left < right。当 left == right 的时候，就是最终结果，无需继续判断。如果用 <=，会造成死循环。（因为left == right 时，满足 left == mid ，会触发 else 分支，但出发后 left 的值没有变，就会一直陷入死循环）

• 求中点：必须使用 left + (right – left + 1) / 2（偏右中点）。

• 口诀：下面出现 -1 的时候（right = mid – 1），上面就加 +1（(right – left + 1) / 2）。

时间复杂度

暴力解法在遍历时每次只能干掉一个数，最坏情况下需要遍历整个数组，时间复杂度为 O(n)。

二分查找每次可以排除一半的数据，即“区间大小”变化为：n → n/2 → n/4 → … → 1。

假设循环执行了 x 次，则 2^x = n，推导出 x = log n。因此二分查找的时间复杂度为 O(log n)。

例题一：二分查找（朴素二分）

题目描述：给定一个 n 个元素有序的整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

解题思路：

• 暴力解法：遍历整个数组，逐个元素与 target 比较，时间复杂度 O(n)。这种方法完全没有利用数组有序这一关键条件，在数据量较大时效率低下，因此需要优化。在思考优化方向时，可以优先从数组有序这一点入手，因为有序性往往意味着可以跳过大量无效比较。

• 抽象出二段性：在数组中随便找一个点，用这个数和 target 比较。比较完之后，这个点会把数组天然地划分成两个区域：一边是小于 target 的部分，另一边是大于 target 的部分。根据这个规律，我们就可以直接舍弃其中一部分，只去另一部分中继续寻找结果，从而大幅缩小搜索范围。

• 本题的二段性很明显：x < t 和 x > t 分居两侧。也就是说，以 target 为分界点，数组被清晰地分成左小右大两个区间，这正是朴素二分能够高效工作的前提。

细节处理：

代码实现：

class Solution {
public int search(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 if (nums[mid] > target) {
right = mid – 1; // 目标在左半区，收缩右边界
} else {
return mid; // 找到目标，返回下标
}
}
return -1; // 循环结束仍未找到，返回 -1
}
}

例题二：在排序数组中查找元素的第一个和最后一个位置（左右边界二分）

题目描述：给定一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果不存在，返回 [-1, -1]。必须设计时间复杂度为 O(log n) 的算法。

解题思路：

• 暴力解法 O(n)，从前往后扫描，当遇见第一个 target 时用一个变量标记，当遇到最后一个 target 时再用一个变量标记，返回这两个变量。

• 朴素二分：数组示例：[ 1, 2, 3, 3, 3, 4, 5 ]，目标值：t = 3，虽然mid一开始就命中了3，但是你是不能确定这个3是起始位置还是终点位置，也有可能是中间值，并且，如果是极端情况，当数组元素全为3时，依然会遍历数组，时间复杂度会变成O(n)，所以，朴素二分是不太合适的

• 因此需要分别寻找左边界和右边界。

1. 查找区间左端点

因为要找左端点，所以将区间分为 <t、≥t 两个部分 ⇒ 二段性

数组示例：[1,2,3,3,3,4,5]，目标 t=3 划分：< t ｜ ≥ t 指针：left、mid、right

逻辑分支：

• ① x<t ⇒ left=mid+1 ⇒ 区间变为新的 [left,right]

• ② x≥t ⇒ right=mid ⇒ 区间变为新的 [left,right]

细节处理：

1. 循环条件：left < right

2. 求中点操作：left + (right – left)  / 2

2. 查找区间右端点

因为要找右端点，所以将区间分为 ≤t、>t 两个部分 ⇒ 二段性

数组示例：[1,2,3,3,3,4,5]，目标 t=3 划分：≤ t ｜ > t 指针：left、mid、right

逻辑分支：

• ① x≤t ⇒ left=mid ⇒区间变为新的 [left,right]

• ② x>t ⇒ right=mid+1 ⇒ 区间变为新的 [left,right]

细节处理：

1. 循环条件：left < right

2. 求中点操作：left + (right – left + 1)  / 2

代码实现：

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;
 ​
         // 1. 查找左端点
         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;
        }
         // 判断是否存在结果（此时 left == right）
         if (nums[left] != target) return ret;
         else ret[0] = left;
 ​
         // 2. 查找右端点
         // 找到左端点后，其实 left 不用再从头开始了，也就是 left=0 这句话可以不写
         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)，mid 防溢出，无脑加加减减

左右边界：while (left < right)。谁“减1”，中点就“加1”

分类讨论的代码，就题论题即可，关键在于理解边界收缩的逻辑

边界情况处理：在做左右边界查找时，务必先处理数组为空、目标值全小于数组、目标值全大于数组等边界情况

2. 习题

二分查找

704.二分查找

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

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

x的平方根

69. x 的平方根 – 力扣（LeetCode）

搜索插入位置

35.搜索插入位置

山脉数组的峰顶索引

852.山脉数组的峰顶索引

寻找峰值

162.寻找峰值

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

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

0~n-1中缺失的数字

LCR 173.点名