二分搜索通常用于在有序的区间内寻找某个目标。如果区间内存在多个目标，还可以区分为寻找左侧边界的二分搜索和寻找右侧边界的二分搜索。
最基本的二分搜索算法：
因为我们初始化 right = nums.length - 1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while (left <= right)
同时也决定了 left = mid + 1 和 right = mid - 1
因为我们只需找到一个 target 的索引即可
所以当 nums[mid] == target 时可以立即返回
寻找左侧边界的二分搜索：
因为我们初始化 right = nums.length -1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while (left <= right)
同时也决定了 left = mid + 1 和 right = mid - 1
因为我们需找到 target 的最左侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧右侧边界以锁定左侧边界
寻找右侧边界的二分搜索：
因为我们初始化 right = nums.length -1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while (left <= right)
同时也决定了 left = mid + 1 和 right = mid - 1
因为我们需找到 target 的最左侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧左侧边界以锁定右侧边界
代码框架：
function binarySearch(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
return -1;
}
function leftBoundSearch(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
// target 比所有数都大
if (left >= nums.length) return -1;
// 类似之前算法的处理方式
return nums[left] === target ? left : -1;
}
function rightBoundSearch(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) {
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
// target 比所有元素都小
if (right < 0) return -1;
// 类似之前算法的处理方式
return nums[right] === target ? right : -1;
}
计算 mid 时需要防止溢出，代码中 left + (right - left) / 2 和 (left + right) / 2 的结果相同，但是有效防止了 left 和 right 太大，直接相加导致溢出的情况。
此外，尤其要注意 mid 为小数的情况，用 Math.floor 和 Math.ceil 处理得到的新区间是不同的。