二分算法：8 道经典题目详解与实战

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

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

思路

这是经典的'查找范围'问题，可以用两次二分查找解决。第一次找第一个出现位置，第二次找最后一个出现位置。时间复杂度为 O(log n)，适合处理排序数组。

步骤

查找第一个位置：使用二分查找，找到目标值的第一个位置。 每次判断 nums[mid] 是否大于等于 target，是则向左移动，否则向右移动。 查找最后一个位置：使用二分查找，找到目标值的最后一个位置。 每次判断 nums[mid] 是否小于等于 target，是则向右移动，否则向左移动。 返回结果：如果找到两个位置，返回它们的范围，否则返回 [-1, -1]。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        // 如果数组为空，直接返回 {-1, -1}
        if (nums.size() == 0) return {-1, -1};
        // 获取数组的大小
        int n = nums.size();
        // 初始化左右边界
        int left = 0, right = n - 1;
        // 查找左端点，目标是找到 target 第一次出现的位置
        while (left < right) {
            // 计算中间索引，防止溢出的安全写法
            int mid = left + (right - left) / 2;
            // 如果中间值小于目标值，说明目标值在右侧，将 left 移到 mid + 1
            if (nums[mid] < target) left = mid + 1;
            // 如果中间值大于等于目标值，右边界移动到 mid，继续查找
            if (nums[mid] >= target) right = mid;
        }
        // 如果左边界的值不等于 target，说明数组中没有该值，返回 {-1, -1}
        if (nums[left] != target) return {-1, -1};
        // 记录找到的目标值的起始位置
        int begin = left;
        // 查找右端点，目标是找到 target 最后一次出现的位置
        right = n - 1;
        // 重新初始化右边界
        // 使用二分查找找右边界
        while (left < right) {
            // 计算中间索引，为了确保 mid 偏向右侧，加 1
            int mid = left + (right - left + 1) / 2;
            // 如果中间值小于等于目标值，说明右边界可能在右侧，将 left 移动到 mid
            if (nums[mid] <= target) left = mid;
            // 如果中间值大于目标值，说明右边界在左侧，将 right 移到 mid - 1
            if (nums[mid] > target) right = mid - 1;
        }
        // 返回目标值的起始和结束位置
        return {begin, right};
    }
};

3.x 的平方根

https://leetcode.cn/problems/sqrtx/

思路

使用二分查找法求 x 的平方根。定义初始范围为 0,x，每次取中间值 m，计算 m²与 x 的比较。如果 m²小于 x，则移动左边界；如果 m²大于 x，则移动右边界。直至找到平方根或其整数部分。

步骤

初始化：设置 left 为 0，right 为 x。 二分查找：计算中点 mid。 如果 mid * mid 小于 x，说明平方根在右侧，更新 left = mid + 1。 如果 mid * mid 大于 x，说明平方根在左侧，更新 right = mid - 1。 终止条件：当 left 和 right 相遇时，取较小值作为结果的整数部分。

class Solution {
public:
    int mySqrt(int x) {
        // 定义二分查找的左右边界
        int left = 1, right = x;
        // 如果 x 小于 1，直接返回 0
        if (x < 1) return 0;
        // 开始二分查找
        while (left < right) {
            // 计算中间值，为了避免溢出，使用 left + (right - left + 1) / 2
            long long mid = left + (right - left + 1) / 2;
            // 如果 mid 的平方小于等于 x，说明 mid 可能是答案，或者答案在右侧，将 left 移动到 mid
            if (mid * mid <= x) left = mid;
            // 如果 mid 的平方大于 x，说明 mid 太大，答案在左侧，将 right 移动到 mid - 1
            else if (mid * mid > x) right = mid - 1;
        }
        // 返回找到的平方根的整数部分
        return left;
    }
};

4.搜索插入位置

https://leetcode.cn/problems/search-insert-position/description/

思路

给定一个有序数组和目标值，要求返回目标值在数组中的插入位置。如果数组中存在目标值，返回其索引；若不存在，返回其应该插入的位置。使用二分查找，找到第一个大于或等于目标值的位置。

步骤

初始化：使用 left 和 right 指针。 二分查找：计算中点 mid。 如果 nums[mid] 大于或等于目标值 target，则将 right 更新为 mid - 1。 否则，将 left 更新为 mid + 1。 终止条件：当 left 和 right 相遇时，left 即为目标值要插入的位置。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size(); // 获取数组的大小
        // 定义左右边界，left 是左边界，right 是右边界
        int left = 0, right = n - 1;
        while (left <= right) {
            // 计算中间索引 mid，避免溢出的安全写法
            int mid = left + (right - left) / 2;
            // 如果中间值小于目标值，说明目标值在右半部分，移动左边界到 mid + 1
            if (nums[mid] < target) left = mid + 1;
            // 如果中间值大于目标值，说明目标值在左半部分，移动右边界到 mid - 1
            if (nums[mid] > target) right = mid - 1;
            // 如果中间值等于目标值，返回当前中间值的索引
            if (nums[mid] == target) return mid;
        }
        // 如果没有找到目标值，返回插入位置 left
        return left;
    }
};

5.山脉数组的峰顶索引

https://leetcode.cn/problems/peak-index-in-a-mountain-array/

思路

山脉数组是先递增后递减的数组，因此其峰顶就是数组中最大值的位置。可以使用二分查找，类似'寻找峰值'的思路，找到这个峰顶索引。

步骤

初始化：使用 left 和 right 指针，分别指向数组的开头和结尾。 二分查找：计算中点 mid。 如果 nums[mid] 大于 nums[mid + 1]，峰顶在左侧，更新 right = mid。 如果 nums[mid] 小于 nums[mid + 1]，峰顶在右侧，更新 left = mid + 1。 终止条件：当 left 和 right 相遇时，left 即为峰顶的索引。

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        // 获取数组大小
        int n = arr.size();
        // 定义左右边界。由于数组两端不能是峰值，山峰一定在 1 到 n-2 之间
        int left = 1, right = n - 2;
        // 当左边界小于右边界时，继续查找
        while (left < right) {
            // 计算中间位置，使用 left + (right - left + 1) / 2 可以避免溢出
            int mid = left + (right - left + 1) / 2;
            // 如果中间元素比左侧的前一个元素小，说明山峰在左边，右边界移动到 mid - 1
            if (arr[mid] < arr[mid - 1]) right = mid - 1;
            // 否则，山峰在右侧或当前位置，左边界移动到 mid
            else left = mid;
        }
        // 循环结束时，left 和 right 会指向同一个位置，这就是峰值的索引
        return left;
    }
};

6.寻找峰值

https://leetcode.cn/problems/find-peak-element/description/

思路

峰值定义为该元素比相邻元素大。可以使用二分查找的变种。每次选择中点，如果中点比其右侧元素小，则峰值在右侧；如果中点比其右侧元素大，则峰值在左侧。这样逐步缩小搜索范围，直至找到峰值。

步骤

初始化：定义 left 和 right 指针。 二分查找：每次计算中点 mid。 如果 nums[mid] 大于 nums[mid + 1]，说明峰值在左侧或就是 mid，更新 right = mid。 如果 nums[mid] 小于 nums[mid + 1]，说明峰值在右侧，更新 left = mid + 1。 终止条件：当 left 和 right 相遇时，left 即为峰值所在的位置。

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        // 初始化左右边界
        int left = 0, right = nums.size() - 1;
        // 二分查找
        while (left < right) {
            // 计算中间索引，避免溢出
            int mid = left + (right - left) / 2;
            // 如果中间值大于它右边的元素，说明峰值在左侧或当前元素是峰值，将右边界移到 mid
            if (nums[mid] > nums[mid + 1]) right = mid;
            // 如果中间值小于它右边的元素，说明峰值在右侧，将左边界移到 mid + 1
            else left = mid + 1;
        }
        // 返回最终找到的峰值索引
        return left;
    }
};

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

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/

思路

旋转排序数组的特点是其包含两个有序的子数组（前一段大于后一段）。最小值通常出现在这两个有序子数组的交界处。可以使用二分查找，比较中点和右端点的值，若中点大于右端点，最小值在右侧；若中点小于右端点，最小值在左侧。

步骤

初始化：定义 left 和 right 指针。 二分查找：每次计算中点 mid。 如果 nums[mid] 大于 nums[right]，说明最小值在右侧，更新 left = mid + 1。 否则，最小值在左侧或当前 mid 处，更新 right = mid。 终止条件：当 left 和 right 相遇时，left 即为最小值所在的位置。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size(); // 获取数组大小
        int left = 0, right = n - 1; // 初始化左右边界
        // 二分查找
        while (left < right) {
            int mid = left + (right - left) / 2; // 计算中间索引，避免溢出
            // 如果中间值大于最右侧值，说明最小值在右侧，更新 left
            if (nums[mid] > nums[right]) left = mid + 1;
            // 否则，最小值在左侧或当前 mid 处
            else right = mid;
        }
        // 最小值在 left 处
        return nums[left];
    }
};

8.JZ53(2) 缺失的数字

《剑指 offer 面试题 53-II》 题目类型：0〜n-1 中缺失的数字（面试题 53 - II） 因为这题作者在 leetcode 中未找到这题原题，不过有一道类似题目 （这题在 leetcode 消失的原因是剑指 offer 在 leetcode 上下架了） https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/

思路

因为数组是排好序的，且数字从 0 到 n-1 连续，可以使用二分查找找到缺失的数字。如果 nums[mid] == mid，说明缺失的数字在右侧；否则在左侧。

class Solution {
public:
    // 该函数通过二分查找处理缺失数字问题，返回缺失的数字
    int missingNumber(vector<int>& records) {
        // 初始化左右边界
        int left = 0, right = records.size() - 1;
        // 执行二分查找
        while (left < right) {
            // 计算中间索引，避免溢出
            int mid = left + (right - left) / 2;
            // 如果记录值等于索引值，继续在右侧查找
            if (records[mid] == mid) left = mid + 1;
            // 否则缩小右侧边界
            else right = mid;
        }
        // 如果最终找到的位置的索引值等于该位置的记录值，则返回 left + 1，否则返回 left
        return left == records[left] ? left + 1 : left;
    }
};

此外这题还可以用 4 种 O(n) 时间复杂度方法去求：第 1 种：直接遍历寻找，第 2 种：哈希，第 3 种：异或，第 4 种：等差求和。