第一个,最基本的二分查找算法:
1 因为我们初始化 right = nums.length - 1
2 所以决定了我们的「搜索区间」是 [left, right]
3 所以决定了 while (left <= right)
4 同时也决定了 left = mid+1 和 right = mid-1
5
6 因为我们只需找到一个 target 的索引即可
7 所以当 nums[mid] == target 时可以立即返回
第二个,寻找左侧边界的二分查找:
1 因为我们初始化 right = nums.length
2 所以决定了我们的「搜索区间」是 [left, right)
3 所以决定了 while (left < right)
4 同时也决定了 left = mid + 1 和 right = mid
5
6 因为我们需找到 target 的最左侧索引
7 所以当 nums[mid] == target 时不要立即返回
8 而要收紧右侧边界以锁定左侧边界
第三个,寻找右侧边界的二分查找:
1 因为我们初始化 right = nums.length
2 所以决定了我们的「搜索区间」是 [left, right)
3 所以决定了 while (left < right)
4 同时也决定了 left = mid + 1 和 right = mid
5
6 因为我们需找到 target 的最右侧索引
7 所以当 nums[mid] == target 时不要立即返回
8 而要收紧左侧边界以锁定右侧边界
9
10 又因为收紧左侧边界时必须 left = mid + 1
11 所以最后无论返回 left 还是 right,必须减一