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

1.二分查找

https://leetcode.cn/problems/binary-search/

思路

标准的二分查找。给定一个有序数组和目标值，每次选择数组的中间元素与目标值比较。如果中间元素等于目标值，则返回该索引；若中间元素小于目标值，则在右侧继续搜索；若中间元素大于目标值，则在左侧继续搜索。时间复杂度为 O(log n)。

步骤

初始化：设置 left 和 right 分别为数组的开头和结尾。 二分查找：计算中点 mid。 如果 nums[mid] 等于目标值，返回 mid。 如果 nums[mid] 小于目标值，更新 left = mid + 1。 如果 nums[mid] 大于目标值，更新 right = mid - 1。 终止条件：如果没有找到，返回 -1。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size(); // 获取数组的大小
        // 定义左右边界，left 是左边界，right 是右边界
        for (int left = 0, right = n - 1; left <= right;) {
            // 计算中间索引 mid，避免溢出的安全写法可以使用：mid = left + (right - left) / 2;
            int mid = (left + right) / 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;
        }
        // 如果没有找到目标值，返回 -1
         ;
    }
};