二分查找全解

// 运行环境：Node.js 14+
// 保存为 dsa-l19.js，执行：node dsa-l19.js

// 模板一：在有序数组找 target（等于即返回）
function binarySearch(a, target) {
  let lo = 0, hi = a.length - 1
  while (lo <= hi) {
    const mid = (lo + hi) >> 1
    if (a[mid] === target) return mid
    if (a[mid] < target) lo = mid + 1
    else hi = mid - 1
  }
  return -1
}

// 模板二：找 target 的"最左"位置（可不存在，返回插入点）
function lowerBound(a, target) {
  let lo = 0, hi = a.length
  while (lo < hi) {
    const mid = (lo + hi) >> 1
    if (a[mid] < target) lo = mid + 1
    else hi = mid
  }
  return lo
}

// 模板三：找 target 的"最右"位置
function upperBound(a, target) {
  let lo = 0, hi = a.length
  while (lo < hi) {
    const mid = (lo + hi) >> 1
    if (a[mid] <= target) lo = mid + 1
    else hi = mid
  }
  return lo
}

// 旋转数组中的最小值（含重复）：[3,4,5,1,2] -> 1
function findMin(nums) {
  let lo = 0, hi = nums.length - 1
  while (lo < hi) {
    const mid = (lo + hi) >> 1
    if (nums[mid] > nums[hi]) lo = mid + 1 // 最小值在右半
    else if (nums[mid] < nums[hi]) hi = mid // 在左半（含 mid）
    else hi--                               // 相等时收缩右界去重
  }
  return nums[lo]
}

// 二分答案：x 的平方根（向下取整）
function mySqrt(x) {
  let lo = 0, hi = x
  while (lo <= hi) {
    const mid = (lo + hi) >> 1
    if (mid * mid <= x) lo = mid + 1
    else hi = mid - 1
  }
  return hi
}

console.log(binarySearch([1,3,5,7], 5))  // 2
console.log(lowerBound([1,2,2,2,3], 2))  // 1
console.log(upperBound([1,2,2,2,3], 2))  // 4
console.log(findMin([3,4,5,1,2]))        // 1
console.log(mySqrt(8))                   // 2