Binary Search

Binary search finds a value in a sorted array by checking the middle and throwing away half the array each step. It's O(log n): about 20 steps for a million items. The array must be sorted first.

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

  while (left <= right) {
    const mid = Math.floor((left + right) / 2)
    if (nums[mid] === target) return mid
    if (nums[mid] < target) left = mid + 1   // search right half
    else right = mid - 1                     // search left half
  }

  return -1  // not found
}

binarySearch([1, 3, 5, 7, 9, 11], 7)  // 3