Warm-up binary search · arrays

Guess the page

Find any page in a 1,000 page book in ten guesses or fewer.

Write binarySearch(sorted, target): sorted holds distinct numbers in ascending order. Return the index of target, or -1 if it is not there. Use binary search: check the middle, then throw away the half that cannot hold the target.

Call show(window) on each guess, where window is sorted with every value outside your current search range replaced by 0. The stage draws the range closing in.

Example: binarySearch([1, 3, 5, 7, 9, 11], 7) returns 3.

Tests you can see

binarySearch([1,3,5,7,9,11], 7)3
binarySearch([2,4,6,8], 5)-1
binarySearch([10,20,30,40,50], 10)0

More tests are hidden. The server runs them all before a time counts.

Call show() while your code works and the run plays back here.

javascriptbinarySearch()

function binarySearch(sorted, target) {
  let lo = 0;
  let hi = sorted.length - 1;
  // while lo <= hi: look at the middle, then move lo or hi
  return -1;
}

function binarySearch(sorted, target) {
  let lo = 0;
  let hi = sorted.length - 1;
  // while lo <= hi: look at the middle, then move lo or hi
  return -1;
}

Tab indents · Cmd/Ctrl+Enter runs