题目链接 · 灵神原题解（署名来源）

视频讲解

请看【基础算法精讲 04】。制作不易，欢迎点赞~

答疑

问：如何理解 end = lowerBound(nums, target + 1) - 1 这段代码？

答：要想找到 $\le \mathit{\text{target}}$ 的最后一个数，无需单独再写一个二分。我们可以先找到这个数的右边相邻数字，也就是 $>\mathit{\text{target}}$ 的第一个数。在所有数都是整数的前提下，$>\mathit{\text{target}}$ 等价于 $\ge \mathit{\text{target}}+1$，这样就可以复用我们已经写好的二分函数了，即 lowerBound(nums, target + 1)。然后将其减一，就得到 $\le \mathit{\text{target}}$ 的最后一个数的下标。

问：如果 $\ge \mathit{\text{target}}+1$ 的第一个数不存在怎么办？

答：这说明数组中的数都 $\le \mathit{\text{target}}$。如果数组中有 $\mathit{\text{target}}$，那么数组的最后一个数（下标 $n-1$）就是 $\mathit{\text{target}}$（因为数组是递增的）。lowerBound(nums, target + 1) 在这种情况下会返回 $n$，减一得到 $n-1$，这正是我们要计算的下标。

问：为什么要写 left + (right - left) / 2？

答：在面试或者实际场景中，你不一定知道输入的数组有多长，万一数组长度达到 $\mathtt{\text{int}}$ 最大值，left + right 可能会发生加法溢出。当然，如果只看本题的数据范围，写 (left + right) / 2 也可以。对于 Python 来说，由于没有溢出这个概念，所以可以直接相加。

问：怎么判断我写的是哪一种二分？

答：看 $\mathtt{\text{while}}$ 循环的条件，如果是 left <= right，就是闭区间；如果是 left < right，就是半闭半开区间；如果是 left + 1 < right，就是开区间。

问：关于闭区间写法，为什么 nums[mid] >= target 成立的时候要写 right = mid - 1？此时的 $\mathit{\text{mid}}$ 不是有可能是答案吗？这样写不会错过答案吗？

答：「二分范围」和「答案所在范围」是两个概念。设现在二分的范围是闭区间 $[L,R]$，如果下标在 $[L,R]$ 中的数都小于 $\mathit{\text{target}}$，根据循环不变量，答案是 $R+1$。由此可见，当我们在闭区间 $[L,R]$ 中二分时，答案所在范围是 $[L,R+1]$。顺带一提，如果题目保证答案在闭区间 $[a,b]$ 中，则可以在 $[a,b-1]$ 中二分，如果这个范围内的数都不满足要求，那么剩下的 $b$ 就是答案（排除所有错误答案后，剩下的一定是正确答案）。

问：我看到一种二分的写法，在二分的过程中，额外记录答案的值。如何评价这种写法？

答：喜欢这种写法的同学，推荐写开区间二分。开区间二分 $\mathtt{\text{if}}$ 条件成立时更新的是哪个变量，最后返回的就是哪个变量。这和记录答案的做法如出一辙。

问：关于开区间二分，如何理解 $-1$ 和 $n$ 这两个下标？

答：可以假设 $\mathit{\text{nums}}[-1]=-\mathrm{\infty }$ 以及 $\mathit{\text{nums}}[n]=\mathrm{\infty }$，此时 $\mathit{\text{nums}}$ 仍然是有序的。在这种情况下，$\mathit{\text{nums}}[-1]<\mathit{\text{target}}$，所以 $-1$ 是红色；$\mathit{\text{nums}}[n]\ge \mathit{\text{target}}$，所以 $n$ 是蓝色。这个思想可以推广到二分答案，见本文末尾的二分题单。

闭区间写法

Python 解法1

class Solution:
    # lower_bound 返回最小的满足 nums[i] >= target 的下标 i
    # 如果数组为空，或者所有数都 < target，则返回 len(nums)
    # 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
    def lower_bound(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1  # 闭区间 [left, right]
        while left <= right:  # 区间不为空
            # 循环不变量：
            # nums[left-1] < target
            # nums[right+1] >= target
            mid = (left + right) // 2
            if nums[mid] >= target:
                right = mid - 1  # 范围缩小到 [left, mid-1]
            else:
                left = mid + 1  # 范围缩小到 [mid+1, right]
        # 循环结束后 left = right+1
        # 此时 nums[left-1] < target 而 nums[left] = nums[right+1] >= target
        # 所以 left 就是第一个 >= target 的元素下标
        return left

    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = self.lower_bound(nums, target)
        if start == len(nums) or nums[start] != target:
            return [-1, -1]  # nums 中没有 target
        # 如果 start 存在，那么 end 必定存在
        end = self.lower_bound(nums, target + 1) - 1
        return [start, end]

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
    // lower_bound 返回最小的满足 nums[i] >= target 的下标 i
    // 如果数组为空，或者所有数都 < target，则返回 nums.size()
    // 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
    int lower_bound(vector<int>& nums, int target) {
        int left = 0, right = (int) nums.size() - 1; // 闭区间 [left, right]
        while (left <= right) { // 区间不为空
            // 循环不变量：
            // nums[left-1] < target
            // nums[right+1] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1; // 范围缩小到 [left, mid-1]
            } else {
                left = mid + 1; // 范围缩小到 [mid+1, right]
            }
        }
        // 循环结束后 left = right+1
        // 此时 nums[left-1] < target 而 nums[left] = nums[right+1] >= target
        // 所以 left 就是第一个 >= target 的元素下标
        return left;
    }

public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int start = lower_bound(nums, target);
        if (start == nums.size() || nums[start] != target) {
            return {-1, -1}; // nums 中没有 target
        }
        // 如果 start 存在，那么 end 必定存在
        int end = lower_bound(nums, target + 1) - 1;
        return {start, end};
    }
};

左闭右开区间写法

Python 解法3

class Solution:
    # lower_bound 返回最小的满足 nums[i] >= target 的下标 i
    # 如果数组为空，或者所有数都 < target，则返回 len(nums)
    # 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
    def lower_bound(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)  # 左闭右开区间 [left, right)
        while left < right:  # 区间不为空
            # 循环不变量：
            # nums[left-1] < target
            # nums[right] >= target
            mid = (left + right) // 2
            if nums[mid] >= target:
                right = mid  # 范围缩小到 [left, mid)
            else:
                left = mid + 1  # 范围缩小到 [mid+1, right)
        # 循环结束后 left = right
        # 此时 nums[left-1] < target 而 nums[left] = nums[right] >= target
        # 所以 left 就是第一个 >= target 的元素下标
        return left

    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = self.lower_bound(nums, target)  # 选择其中一种写法即可
        if start == len(nums) or nums[start] != target:
            return [-1, -1]  # nums 中没有 target
        # 如果 start 存在，那么 end 必定存在
        end = self.lower_bound(nums, target + 1) - 1
        return [start, end]

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
    // lower_bound 返回最小的满足 nums[i] >= target 的下标 i
    // 如果数组为空，或者所有数都 < target，则返回 nums.size()
    // 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
    int lower_bound(vector<int>& nums, int target) {
        int left = 0, right = nums.size(); // 左闭右开区间 [left, right)
        while (left < right) { // 区间不为空
            // 循环不变量：
            // nums[left-1] < target
            // nums[right] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid; // 范围缩小到 [left, mid)
            } else {
                left = mid + 1; // 范围缩小到 [mid+1, right)
            }
        }
        // 循环结束后 left = right
        // 此时 nums[left-1] < target 而 nums[left] = nums[right] >= target
        // 所以 left 就是第一个 >= target 的元素下标
        return left;
    }

public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int start = lower_bound(nums, target);
        if (start == nums.size() || nums[start] != target) {
            return {-1, -1}; // nums 中没有 target
        }
        // 如果 start 存在，那么 end 必定存在
        int end = lower_bound(nums, target + 1) - 1;
        return {start, end};
    }
};

开区间写法

Python 解法5

class Solution:
    # lower_bound 返回最小的满足 nums[i] >= target 的下标 i
    # 如果数组为空，或者所有数都 < target，则返回 len(nums)
    # 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
    def lower_bound(self, nums: List[int], target: int) -> int:
        left, right = -1, len(nums)  # 开区间 (left, right)
        while left + 1 < right:  # 区间不为空
            mid = (left + right) // 2
            # 循环不变量：
            # nums[left] < target
            # nums[right] >= target
            if nums[mid] >= target:
                right = mid  # 范围缩小到 (left, mid)
            else:
                left = mid  # 范围缩小到 (mid, right)
        # 循环结束后 left+1 = right
        # 此时 nums[left] < target 而 nums[right] >= target
        # 所以 right 就是第一个 >= target 的元素下标
        return right

    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = self.lower_bound(nums, target)  # 选择其中一种写法即可
        if start == len(nums) or nums[start] != target:
            return [-1, -1]  # nums 中没有 target
        # 如果 start 存在，那么 end 必定存在
        end = self.lower_bound(nums, target + 1) - 1
        return [start, end]

C++ 解法5

// C++ 版待补充

C++ 解法6

class Solution {
    // lower_bound 返回最小的满足 nums[i] >= target 的下标 i
    // 如果数组为空，或者所有数都 < target，则返回 nums.size()
    // 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
    int lower_bound(vector<int>& nums, int target) {
        int left = -1, right = nums.size(); // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // nums[left] < target
            // nums[right] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid; // 范围缩小到 (left, mid)
            } else {
                left = mid; // 范围缩小到 (mid, right)
            }
        }
        // 循环结束后 left+1 = right
        // 此时 nums[left] < target 而 nums[right] >= target
        // 所以 right 就是第一个 >= target 的元素下标
        return right;
    }

public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int start = lower_bound(nums, target);
        if (start == nums.size() || nums[start] != target) {
            return {-1, -1}; // nums 中没有 target
        }
        // 如果 start 存在，那么 end 必定存在
        int end = lower_bound(nums, target + 1) - 1;
        return {start, end};
    }
};

C++ 解法7

class Solution {
    // lower_bound 返回最小的满足 nums[i] >= target 的下标 i
    // 如果数组为空，或者所有数都 < target，则返回 nums.size()
    // 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
    int lower_bound(vector<int>& nums, int target) {
        int left = -1, right = nums.size(); // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // nums[left] < target
            // nums[right] >= target
            int mid = left + (right - left) / 2;
            (nums[mid] >= target ? right : left) = mid; // 注：只有开区间二分可以这样写
        }
        // 循环结束后 left+1 = right
        // 此时 nums[left] < target 而 nums[right] >= target
        // 所以 right 就是第一个 >= target 的元素下标
        return right;
    }

public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int start = lower_bound(nums, target);
        if (start == nums.size() || nums[start] != target) {
            return {-1, -1}; // nums 中没有 target
        }
        // 如果 start 存在，那么 end 必定存在
        int end = lower_bound(nums, target + 1) - 1;
        return {start, end};
    }
};

附：库函数写法

注：Java 的 Arrays.binarySearch，在数组包含多个 $\mathit{\text{target}}$ 的情况下，返回的不一定是第一个 $\ge \mathit{\text{target}}$ 的元素下标，所以无法使用。

Python 解法8

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = bisect_left(nums, target)
        if start == len(nums) or nums[start] != target:
            return [-1, -1]
        end = bisect_right(nums, target) - 1
        return [start, end]

C++ 解法8

// C++ 版待补充

C++ 解法9

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        // 也可以用 equal_range，见【C++ 写法二】
        int start = ranges::lower_bound(nums, target) - nums.begin();
        if (start == nums.size() || nums[start] != target) {
            return {-1, -1};
        }
        int end = ranges::upper_bound(nums, target) - nums.begin() - 1;
        return {start, end};
    }
};

C++ 解法10

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        auto [start, end] = ranges::equal_range(nums, target);
        if (start == end) {
            return {-1, -1};
        }
        return {(int) (start - nums.begin()), (int) (end - nums.begin() - 1)};
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(\log n)$，其中 $n$ 是 $\mathit{\text{nums}}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。

二分查找常用转化表

需求	写法	如果不存在
$\ge x$ 的第一个元素的下标	$\mathtt{\text{lowerBound}}(\mathit{\text{nums}},x)$	结果为 $n$
$>x$ 的第一个元素的下标	$\mathtt{\text{lowerBound}}(\mathit{\text{nums}},x+1)$	结果为 $n$
$<x$ 的最后一个元素的下标	$\mathtt{\text{lowerBound}}(\mathit{\text{nums}},x)-1$	结果为 $-1$
$\le x$ 的最后一个元素的下标	$\mathtt{\text{lowerBound}}(\mathit{\text{nums}},x+1)-1$	结果为 $-1$

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府