【数组】二分查找

[miracles1919]

参考：我作了首诗，保你闭着眼睛也能写对二分查找

上模板

function binarySearch(nums, target) {
  let left = 0, right = nums.length - 1

  while (...) {
    let mid = left + (right - left) / 2
    if (nums[mid] === target) {
      // ...
    } else if (nums[mid] < target) {
      left = ...
    } else if (nums[mid] > target) {
      right = ...
    }
  }
  return ...
}

[miracles1919]

704. 二分查找

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
    let left = 0, right = nums.length - 1
    while (left <= right) {
        let mid = left + ((right - left) >> 1)
        if (nums[mid] === target) {
            return mid
        } else if (nums[mid] < target) {
            left = mid + 1
        } else if (nums[mid] > target) {
            right = mid - 1
        }
    }
    return -1
};

Or nums.indexOf(target) 🤫

[miracles1919]

查找左侧边界的二分查找

例如，nums = [5, 7, 7, 8, 8, 10], target = 8

function leftSearch (nums, target) {
    let left = 0, right = nums.length
    // [left, right)
    while (left < right) {
        let mid = left + ((right - left) >> 1)
        if (nums[mid] === target) {
            right = mid // 继续收缩
        } else if (nums[mid] < target) {
            left = mid + 1
        } else if (nums[mid] > target) {
            right = mid // 为什么不是mid - 1, 因为right不包含
        }
    }
    if (left >= nums.length || nums[left] !== target) return -1
    return left
};

查找右侧边界的二分查找

function rightSearch (nums, target) {
    let left = 0, right = nums.length
    // [left, right)
    while (left < right) {
        let mid = left + ((right - left) >> 1)
        if (nums[mid] === target) {
            left = mid + 1 // 收缩左侧
        } else if (nums[mid] < target) {
            left = mid + 1
        } else if (nums[mid] > target) {
            right = mid
        }
    }
    if (left - 1 >= nums.length || nums[left - 1] !== target) return -1
    return left - 1
};