JS实现二分搜索及其变种

function binarySearch(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] === target) return mid;
    nums[mid] < target ? (left = mid + 1) : (right = mid - 1);
  }
  return -1;
}

function lowerBound(nums, target) {
  let left = 0, right = nums.length;
  while (left < right) {
    const mid = left + ((right - left) >> 1);
    nums[mid] >= target ? (right = mid) : (left = mid + 1);
  }
  return left;
}

function upperBound(nums, target) {
  let left = 0, right = nums.length;
  while (left < right) {
    const mid = left + ((right - left) >> 1);
    nums[mid] <= target ? (left = mid + 1) : (right = mid);
  }
  return left - 1;
}

要点：1) 循环条件 left <= right 与 left < right 的区别；2) 边界更新 mid ± 1 还是 mid；3) 适用于有序数组，O(log n)。变种：旋转数组搜索、寻找峰值、Sqrt(x)。