Patterns

Find an exact value (or report not found) in a sorted array

When to useSorted array; need to find a specific value or position

iterative

INITIALIZE

lo = 0, hi = arr.length - 1

let lo = 0, hi = arr.length - 1;

let lo = 0, hi = arr.length - 1, ans = -1;

let lo = 0, hi = arr.length - 1;

—

TRAVERSE

while (lo <= hi)

while (lo <= hi) {

while (lo <= hi) {

while (lo <= hi) {

—

mid

mid = Math.floor((lo + hi) / 2)

  const mid = Math.floor((lo + hi) / 2);

  const mid = Math.floor((lo + hi) / 2);

  const mid = Math.floor((lo + hi) / 2);

—

[COMPARE]

if equal return; if less lo = mid+1; else hi = mid-1

  if (arr[mid] === target) return true;
  if (arr[mid] < target) lo = mid + 1;
  else hi = mid - 1;

  if (arr[mid] === target) { ans = mid; hi = mid - 1; }
  else if (arr[mid] < target) lo = mid + 1;
  else hi = mid - 1;

  if (arr[mid] === target) return mid;
  if (arr[mid] < target) lo = mid + 1;
  else hi = mid - 1;

—

RETURN

return -1 (not found)

return false;

return ans;

return -1;

—