Binary Search

Complexcity: O(LOG N)

Recursive implementation:

export default function bs_list(haystack: number[], needle: number): boolean {
  let m = Math.round(haystack.length / 2);
  if (haystack.length == 1) {
    return haystack[0] == needle;
  }

  let left = haystack.slice(0, m);
  let right = haystack.slice(m, haystack.length);
  let cur = haystack[m-1];
  if (cur == needle) {
    return true
  } else if (needle > cur) {
    return bs_list(right, needle)
  } else {
    return bs_list(left, needle)
  }
}

Do while implementation:

export default function bs_list(haystack: number[], needle: number): boolean {
  let lo = 0;
  let hi = haystack.length
  do {
    const m = Math.floor(lo + (hi - lo) / 2);
    const v = haystack[m];
    if (v === needle) {
      return true
    } else if (v > needle) {
      hi = m;
    } else {
      lo = m + 1;
    }
  } while (lo < hi);
  return false;
}

Using binary search in advance problem.

Given two crystal balls that will break if dropped from high enough distance, determine the exact spot in which it will break in the most optimized way.

export default function two_crystal_balls(breaks: boolean[]): number {
  const jump = Math.floor(Math.sqrt(breaks.length));

  let i = jump;
  for (; i< breaks.length; i += jump) {
    if (breaks[i]) {
      break
    }
  }

  i -= jump;

  for (let j = 0; j < jump && i < breaks.length; ++j, ++i) {
    if (breaks[i]) {
      return i;
    }
  }

  return -1;
}