二分查找的默认写法都是left <= right 最后跳出条件就是right, left

1
2
3
4
5
6
7
if (nums[mid] == target) {
    // break
} else if (nums[mid] > target) {
    right = mid - 1;
} else {
    left = mid + 1;
}

如果只需要单边查找（也就是不特殊处理==target，通常是找最大的小于或者最小的大于某一个值的情况），就用left < right

此时的跳出条件是left = right

1
2
3
4
5
6
if (nums[mid] < target) {
  left = mid + 1;
} else {
  right = mid; 
}
// 单边查找，找到 == target的第一个value

这种情况下，如果是left变更（也就是left = mid），mid的计算就是left + (right - left + 1) / 2

这是因为下取整，left可能不会变，所以需要+1来上取整

否则（right = mid的情况），直接left + (right - left) / 2 即可

这一题：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

就是典型的单边查找的情况