二分法

• 前提条件

这道题目的前提是数组为有序数组。 要求 O(log n) 时间复杂度， 如果你用线性扫描，复杂度是 O(n)，直接违规。同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的。

• 704注意

1. 二分查找涉及的很多的边界条件，大家写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

2. 避免越界/ 防止整型溢出可以写mid=left+(right-left)/2。

3. 在二分查找中，mid的计算必须在 while循环内部，因为 left 和right在每次迭代中会动态更新。如果 mid 在循环外部定义（例如，放在 int right之后），它只计算一次，后续迭代中 mid 的值不会随 left 和 right 的变化而更新。

4. 左闭右闭：两端都是有效元素；所以 r 必须是合法下标 → 最大是n - 1
   left<=right，[1，1]里=是有意义的，此时数组中有且仅有1这个数值。
   if(nums[mid] > target){right = mid - 1;}，因为是左闭右闭，此时if已经判断出mid不是我们要找的，直接 - 1，不 - 1会超时。

5. 左闭右开：左端有效；右端只是边界，不是元素
   int right = nums.size();，r 可以等于 n，因为我们根本不会访问 nums[r]
   while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的。
   if (nums[mid] > target) {right = mid;}，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为mid，即：下一个查询区间不会去比较nums[mid]。

• 35注意

1. 返回数组中第一个 >= target 的位置

2. 我们用闭区间 [left, right]，并且始终维护不变量:
   [0, left)：一定 < target；(right, n-1]：一定 ≥ target；[left, right]：未知区间

3. nums[mid] < target;left = mid + 1;此时左边一定没有target;
   nums[mid] >= target;right = mid - 1;mid可能就是答案，但右边一定不是更优解;
   就这样不断缩小区间

4. 当循环结束时，[0,left)左边没target，left本身是第一个 >= target 的位置

1️⃣ 区间模型统一（闭区间 or 半开区间）
2️⃣ 每次更新都严格缩小区间
3️⃣ 循环不变量正确维护

• 34注意

1. left boundary = 第一个 ≥ target 的位置
   right boundary = 最后一个 ≤ target 的位置 = 第一个 > target 的位置 - 1

2. 闭区间：right 是“元素” → 用 n-1
   半开区间：right 是“边界” → 用 n