二分查找算法详解与经典题解

• 若 nums[mid] >= target，说明 mid 可能是结果或结果在左边，保留 mid，令 right = mid。
• 若 nums[mid] < target，说明结果在右边，令 left = mid + 1。 这里 mid 需向下取整，防止 left = mid + 1 导致死循环。

寻找右边界： 我们要找的是最后一个等于 target 的位置。区间特点为：左侧小于等于 target，右侧大于 target。

• 若 nums[mid] <= target，说明 mid 可能是结果或结果在右边，保留 mid，令 left = mid。
• 若 nums[mid] > target，说明结果在左边，令 right = mid - 1。 这里 mid 需向上取整（即 +1），防止 right = mid - 1 导致死循环。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return {-1, -1};
        
        // 找左边界
        int left = 0, right = nums.size() - 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 {-1, -1};
        int begin = left;
        
        // 找右边界
        left = 0; right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        return {begin, right};
    }
};

3. 搜索插入位置

如果目标不存在，需要返回它应该插入的位置。这其实是一个寻找'第一个大于等于 target 的元素'的问题。

思路：

• 若 nums[mid] >= target，说明插入点在 mid 或其左侧，令 right = mid。
• 若 nums[mid] < target，说明插入点在 mid 右侧，令 left = mid + 1。 循环结束时 left == right，即为插入位置。

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

4. x 的平方根

求一个非负整数 x 的平方根的整数部分。虽然可以用暴力枚举，但二分法效率更高。

思路：

• 区间 [0, x] 具有二段性：小于等于 sqrt(x) 的数平方后小于等于 x，大于的则大于 x。
• 注意乘法可能溢出，使用 long long 存储中间结果。
• 若 mid * mid <= x，说明 mid 可能是答案或答案在右边，令 left = mid（需向上取整）。
• 否则令 right = mid - 1。

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

5. 山脉数组的峰顶索引

山脉数组先严格递增再严格递减。我们需要找到峰值的索引。

思路：

• 比较 arr[mid] 与 arr[mid-1]。
• 若 arr[mid] > arr[mid-1]，说明处于上升阶段，峰值在右侧，令 left = mid。
• 若 arr[mid] < arr[mid-1]，说明处于下降阶段，峰值在左侧，令 right = mid - 1。
• 同样需要注意 mid 的取整方式以避免死循环。

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 1, right = arr.size() - 2;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (arr[mid] > arr[mid - 1]) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

6. 寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。数组两端可视为负无穷。

思路：

• 只要存在一段单调递增或递减的区域，就能确定峰值在哪一侧。
• 比较 nums[mid] 和 nums[mid+1]。
• 若 nums[mid] < nums[mid+1]，说明右侧有上升趋势，峰值必在右侧，令 left = mid + 1。
• 否则，峰值在左侧（包括 mid），令 right = mid。

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1]) left = mid + 1;
            else right = mid;
        }
        return left;
    }
};

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

数组原本是升序，但在某个点进行了旋转。例如 [3,4,5,1,2]。

思路：

• 利用旋转特性，数组分为两段：前段大，后段小。
• 比较 mid 与右端点 nums[right]。
• 若 nums[mid] > nums[right]，说明 mid 在前段，最小值在右侧，令 left = mid + 1。
• 若 nums[mid] <= nums[right]，说明 mid 在后段，最小值在左侧（含 mid），令 right = mid。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) left = mid + 1;
            else right = mid;
        }
        return nums[left];
    }
};

8. 点名（缺失的数字）

在一个升序数组中，有一个数字缺失。数组下标从 0 开始，正常情况下 nums[i] == i。

思路：

• 缺失位置之前，nums[i] == i；缺失位置之后，nums[i] > i。
• 这是一个典型的二段性问题。
• 若 nums[mid] == mid，说明缺失在右侧，令 left = mid + 1。
• 否则，缺失在左侧（含 mid），令 right = mid。
• 最后检查 left 是否越界或对应值是否匹配，处理边界情况。

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int left = 0, right = records.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mid == records[mid]) left = mid + 1;
            else right = mid;
        }
        if (left == records[left]) return left + 1;
        return left;
    }
};