Binary Search

If we sort the students array (or keep it sorted as we add/remove students), we can apply a more efficient searching algorithm called Binary Search.

Binary search makes clever use of the knowledge that the data is sorted to consider a (much smaller) subset of elements in finding the target.

Here is how it works:

  • Compare the target value to the middle element of the array.
  • If they are equal, you found the target!
  • If the target is larger than the middle element, you know the target is not in the first half of the array (because the array is sorted), so you can ignore the first half and repeat the search process for the second half.
  • If the target is smaller than the middle element, ignore the second half and repeat the search process for the first half.

By following the process described above, you are (approximately) halving the search space at every step. Eventually, you either find the target or run out of elements (in which case you would report "target not found!")

Binary search is also called "half-interval search" or "binary chop", both of which are more descriptive names for what it does.

Demo

The following demo shows a schematic representation of the Binary Search process.

Notice, in the demo, the target is found after 3 steps (comparisons); Linear search would have needed 6 comparisons to find the target (assuming we start on the left side of the array with the smallest element).

Resources