政务网站的建设原则seo助理

题目

704. 二分查找 - 力扣（LeetCode）

思路

初始化左右指针：left = 0, right = nums.size() - 1

当 left <= right 时，循环执行：

• 计算中间索引：mid = left + (right - left) / 2

• 比较 nums[mid] 与 target：

• 若相等，返回 mid（找到目标）

• 若 nums[mid] < target，更新 left = mid + 1（目标在右半部分）

• 若 nums[mid] > target，更新 right = mid - 1（目标在左半部分）

若循环结束仍未找到目标，返回 -1

过程

以 nums = [-1, 0, 3, 5, 9, 12], target = 9 为例：

初始状态:

索引:  0   1   2   3   4   5
数组: [-1,  0,  3,  5,  9, 12]left         mid        right↓            ↓          ↓0            2          5

 第一次迭代:

• mid = 0 + (5-0)/2 = 2

• nums[mid] = 3 < 9

• 目标在右侧，更新 left = mid + 1 = 3

索引:  0   1   2   3   4   5
数组: [-1,  0,  3,  5,  9, 12]left  mid  right↓     ↓    ↓3     4    5

第二次迭代:

• mid = 3 + (5-3)/2 = 4

• nums[mid] = 9 == 9

• 找到目标，返回 mid = 4

关键点

1. 循环条件：left <= right 确保所有元素都被检查

1. 中点计算：mid = left + (right - left) / 2 避免整数溢出

1. 区间更新：

• left = mid + 1（排除中点及左侧）

• right = mid - 1（排除中点及右侧）

1. 终止条件：找到目标或 left > right（搜索区间为空）

时间与空间复杂度

O(log n)，每次迭代将搜索空间减半

O(1)，只使用常数额外空间

读者可能出现的错误写法

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

 在条件判断中，你比较的是 mid 与 target，但应该比较的是 nums[mid] 与 target。mid 只是索引值，而不是数组中的元素值。

if-if-else 结构有问题。第二个 if 应该是 else if，否则当 mid < target 时，会同时执行第二个条件判断，可能导致错误的结果

循环条件是 while(left < right)，这可能会导致某些情况下漏检查一个元素。

当 left == right 时，循环会终止，但此时还有一个元素（nums[left] 或等价的 nums[right]）没有被检查。如果目标值恰好在这个位置，算法会错误地返回 -1。

正确的写法

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