二分查找算法详解与实战题解

注意：此时 right = mid，为防止死循环，mid 需向下取整。

寻找右边界

右边界的特点是：左侧区间（含边界）小于等于目标值，右侧区间大于目标值。

• 若 nums[mid] <= target，说明 mid 可能是结果或结果在右侧，保留 mid，令 left = mid。
• 若 nums[mid] > target，说明结果在左侧，令 right = mid - 1。

注意：此时 left = mid，为防止死循环，mid 需向上取整（即 mid = left + (right - left + 1) / 2）。

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};
    }
};

搜索插入位置

如果目标不存在，需要返回它应该插入的位置。逻辑与寻找左边界类似：

• 若 nums[mid] >= target，说明插入点在左侧或就是 mid，令 right = mid。
• 若 nums[mid] < target，说明插入点在右侧，令 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;
    }
};

x 的平方根

求 sqrt(x) 等价于寻找最大的整数 i，使得 i * i <= x。这是一个典型的单调性问题，可以使用二分查找优化暴力枚举。

• 区间 [0, x] 分为两部分：平方后小于等于 x 的部分，和大于 x 的部分。
• 注意 mid * mid 可能溢出 int，建议使用 long long。

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;
    }
};

山脉数组的峰顶索引

山脉数组先增后减，峰顶满足 arr[i] > arr[i-1] && arr[i] > arr[i+1]。利用单调性进行二分：

• 若 arr[mid] > arr[mid-1]，说明处于上升阶段，峰顶在右侧，left = mid。
• 否则处于下降阶段，峰顶在左侧，right = mid - 1。

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;
    }
};

寻找峰值

峰值定义为比相邻元素大的数。题目保证至少存在一个峰值。关键在于比较 mid 和 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;
    }
};

旋转排序数组中的最小值

旋转数组可视为两个有序子数组拼接。最小值位于第二个子数组的第一个元素。

• 比较 mid 与右端点 nums[right]：
  • 若 nums[mid] > nums[right]，说明 mid 在第一个递增段，最小值在右侧，left = mid + 1。
  • 若 nums[mid] <= nums[right]，说明 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];
    }
};

缺失的数字

在升序数组中，若没有缺失数字，则 nums[i] == i。一旦缺失，后续元素将不再等于下标。

• 若 nums[mid] == mid，说明缺失点在右侧，left = mid + 1。
• 否则缺失点在左侧，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;
    }
};