binary-search.algo

binary-search.md

Binary Search

1. set min to 0 and max to array length
2. compute guess as the result of (min + max)/2 rounded down
3. if guess is greater than target value then I set max to guess - 1
4. if guess is lesser than target value then I set min to guess + 1
5. if guess is equal to target value I return guess
6. if max < min or min > max then the target value is not contained in array
7. if guess is not equal to target value I return to step 2.

pseudo-code

function binarySearch(array, target)
  min = 0
  max = array.length
  
  do
    guess = (min + max)/2
    if(guess > target)
      max = guess - 1
    else if(guess < target)
      min = guess + 1
    if(max < min || min > max)
      return -1
  while (guess !== target)
  
  return guess