A+DS

Binary Search

Half the search space every step.

Like guessing a number between 1 and 100 with "higher/lower" hints. Instead of checking every element, you look at the middle. If it's too small, eliminate the left half. Too big? Eliminate the right. Each step cuts the remaining elements in half.

  [ ?  ?  ?  ?  M  ?  ?  ?  ? ]
                 ↑
              check middle

  target > M? → search right half
  target < M? → search left half
  target = M? → FOUND!

How it works

  1. 1Array must be sorted
  2. 2Look at the middle element
  3. 3If it matches the target, done!
  4. 4If too small, search the right half; if too big, search the left half

Loading...