Binary Search





Definition: A process designed to search for a specified value in an ordered list (this is important!). The search is done by finding the middle element in the list and comparing it to the value being searched for. The list is then narrowed based on this calculation and the process is repeated until the specified target is found or the list size equals zero.



Real Life Example: You are reading a book with pages 1-400 and would like to turn to page 250. Instead of flipping through each individual page, you find the median page of the book (rounded down) which is page 200. You know that page 250 is greater than 200, so you change the range of pages to look for 250 in from 1-400 to 201-400. Finding the floored median again in the new range, you get 300, leaving you with a range of 201-299 due to 250 being less than 300. The median of the 201-299 range is 250, meaning that you have arrived at your target.



Procedure:

  1. Make sure the list is sorted in a defined order (ex: ascending or descending).
  2. Find the median (middle) element of the list. If the list has an even size, use the lesser of the two middle elements.
  3. Compare the median element to the target. If the median > target, eliminate all values to the right of the median (including the median). If the target > median, eliminate all values to the left of the median (including the median).
  4. Repeat steps 2 and 3 until the target value is found as the median or until you run out of values in the list.

Fun Fact: Binary search is much more efficient than linear search. In a list of 10,000 elements of sorted data, a binary search would take no more than 14 executions to find any piece of data in the list. A linear search could take up to 10,000.



Commonly Used In: