二分查找.md

二分查找

在非递减排序中查找目标元素索引

普通二分查找

var binarySearch = function (nums, target) {
  let left = 0
  let right = nums.length - 1
  while (left <= right) {
    const mid = Math.floor((left + right) / 2)
    const val = nums[mid]
    if (target === val) {
      return mid
    } else if (target > val) {
      left = mid + 1
    } else if (target < val) {
      right = mid - 1
    }
  }
  return -1
}

左侧边界二分查找

var binaryLeftSearch = function (nums, target) {
  let left = 0
  let right = nums.length - 1
  while (left <= right) {
    const mid = Math.floor((left + right) / 2)
    const val = nums[mid]
    if (target > val) {
      left = mid + 1
      // 收紧右侧边界，向左侧边界寻找
    } else if (target <= val) {
      right = mid -1
    }
  }
  if (nums[left] !== target) {
    return -1
  }
  return left
}

右侧边界二分查找

var binaryRightSearch = function (nums, target) {
  let left = 0
  let right = nums.length - 1
  while (left <= right) {
    const mid = Math.floor((left + right) / 2)
    const val = nums[mid]
    // 收紧左侧边界，向右侧边界寻找
    if (target >= val) {
      left = mid + 1
    } else if (target < val) {
      right = mid -1
    }
  }
  if (nums[right] !== target) {
    return -1
  }
  return right
}