Binary Search

Binary search works if the array is already sorted. Split the array in half, and, if the value you’re looking for is less than the element in the middle, you search the left half, if it’s bigger - the right half. Happy case - it’s the middle. Each half is searched in the same manner.

As we always half the array, the number of times you’re reducing the search space, going, for example, 2048→1024→512→…→1, is logN in base 2

O(N) = logN

N/(2^k) = 1

Approach: [lo, hi) - Half open range, High is exclusive, Low is inclusive, lo ⇐ index < hi and size of the array is hi - lo

export default function bs_list(haystack: number[], needle: number): boolean {
  let lo = 0;
  let hi = haystack.length;
 
  while (lo < hi) {
    // offset + the middle
    const midpoint = Math.floor(lo + (hi - lo) / 2);
    const mid_value = haystack[midpoint];
 
    if (needle === mid_value) {
      return true;
    }
 
    if (needle < mid_value) {
      // High is exclusive
      hi = midpoint;
    } else {
      // Midpoint is already checked, don't do it again
      lo = midpoint + 1;
    }
  }
 
  return false;
}

Using floor biases the midpoint toward the lower half, and when we have hi = midpoint we do not skip anything.

I mean, technically we can use ceil too, and bias towards the upper half, but we would have to change the starting hi to be the length - 1, and change the hi and lo setting to be midpoint + 1 and just midpoint respectively, and the condition to be lo <= hi.