Front end interview algorithm — binary search and binary search for left (right) side boundary

1. Ordinary binary search

function binarySearch(nums, target) {
  let left = 0
  let right = nums.length - 1
  while (left <= right) {
    // Use this notation instead of (left+right)/2 to prevent overflow
    const mid = left + parseInt((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
}

binarySearch([1.2.3.4.5].3) / / 2
Copy the code

2. Look for the left edge

function bsLeftBound(nums, target) {
  let left = 0
  let right = nums.length - 1
  while (left <= right) {
    const mid = left + parseInt((right - left) / 2)
    if (nums[mid] === target) {
      right = mid - 1 / /!!!!! Look for the far left of Target, so if you find target, narrow the range to the left of the current location
    } else if (nums[mid] < target) {
      left = mid + 1
    } else if (nums[mid] > target) {
      right = mid - 1}}/ /!!!!! If target exists in nums, then left is its index; If there is none and the last bit is smaller than target, left will be nums.length (out of range), if there is none and the last bit is larger than target, left will be the last bit of NUMs
  returnleft === nums.length || nums[left] ! = target ? -1 : left
}
bsLeftBound([1.3.3.3.3.4].3) / / 1
bsLeftBound([1.2.2.2.2.2].3) Left === nums.length
bsLeftBound([1.2.2.2.2.4].3) Left :5, right:4 satisfy nums[left]! = target
Copy the code

3. Look for the right boundary

function bsRightBound(nums, target) {
  let left = 0
  let right = nums.length - 1
  while (left <= right) {
    const mid = left + parseInt((right - left) / 2)
    if (nums[mid] === target) {
      left = mid + 1 / /!!!!! Look for the extreme right of Target, so if you find target, narrow the range to the right of the current location
    } else if (nums[mid] < target) {
      left = mid + 1
    } else if (nums[mid] > target) {
      right = mid - 1}}/ /!!!!! If target exists in nums, then right is its index; If there is no digit and the digit is smaller than target, right will be numS digit, if there is no digit and the digit is larger than target, right will be -1
  return right < 0|| nums[right] ! = target ? -1 : right
}

bsRightBound([1.3.3.3.3.4].3) / / 4
bsRightBound([2.4.4.4.4.4].3) Left :1, right:0 nums[right]! = target
bsRightBound([4.5.5.5.5.5].3) Left :0, right:-1 right < 0
Copy the code