LC 704. Binary Search

The problem

Solution - $O(\log n)$ Time

This problem is fairly important given that knowing how to do it opens up a large category of problems. Since the array is assumed to be sorted already, I iteratively check within a search window that is the values within the left and right pointers. If the target is above the middle, shift left above the middle and vice versa. This process either closes in on the target while avoiding having to iterate through many values in the array - basically cutting off half of the search window on every iteration.

function search(nums: number[], target: number): number {
  let leftPointer = 0
  let rightPointer = nums.length - 1
  while(leftPointer <= rightPointer) {
    const mid = Math.floor((rightPointer + leftPointer) / 2)
    if (target === nums[mid]) {
      return mid
    } else if (target < nums[mid]) {
      rightPointer = mid - 1
    } else {
      leftPointer = mid + 1
    }
  }
  return -1
};