2.2 Binary search

Linear search vs. binary search

Linear search may require searching all list elements, which can lead to long runtimes. For example, searching for a contact on a smartphone one-by-one from first to last can be time consuming. Because a contact list is sorted, a faster search, known as binary search, checks the middle contact first. If the desired contact comes alphabetically before the middle contact, binary search will then search the first half and otherwise the last half. Each step reduces the contacts that need to be searched by half.

Activity 1: Using binary search to search a contact list.

A contact list is searched for Bob. Assume the following contact list: Amy, Bob, Chris, Holly, Ray, Sarah, Zoe

  1. What is the first contact searched?
  2. What is the second contact searched?

Binary search algorithm

Binary search is a faster algorithm for searching a list if the list's elements are sorted and directly accessible (such as an array). Binary search first checks the middle element of the list. If the search key is found, the algorithm returns the matching location. If the search key is not found, the algorithm repeats the search on the remaining left sublist (if the search key was less than the middle element) or the remaining right sublist (if the search key was greater than the middle element).


Binary search algorithm

Input/Output
NUMBERS: 2 4 7 10 11 32 45 87 
Enter a value: 10
Found 10 at index 3.
...
NUMBERS: 2 4 7 10 11 32 45 87 
Enter a value: 17
17 was not found. 

Activity 2: Binary search algorithm execution.

Given list: ( 4, 11, 17, 18, 25, 45, 63, 77, 89, 114 ).

  1. How many list elements will be checked to find the value 77 using binary search?
  2. How many list elements will be checked to find the value 17 using binary search?
  3. Given an array with 32 elements, how many list elements will be checked if the key is less than all elements in the list, using binary search?

Binary search efficiency

Binary search is incredibly efficient in finding an element within a sorted list. During each iteration or step of the algorithm, binary search reduces the search space (i.e., the remaining elements to search within) by half. The search terminates when the element is found or the search space is empty (element not found). For a 32 element list, if the search key is not found, the search space is halved to have 16 elements, then 8, 4, 2, 1, and finally none, requiring only 6 steps. For an N element list, the maximum number of steps required to reduce the search space to an empty sublist is [log N + 1] Ex: [log 32] + 1 = 6.

If each comparison takes 1 µs (1 microsecond), a binary search algorithm's runtime is at most 20 µs to search a list with 1,000,000 elements, 21 µs to search 2,000,000 elements, 22 µs to search 4,000,000 elements, and so on. Ex: Searching Amazon's online store, which has more than 200 million items, requires less than 28 µs; up to 7,000,000 times faster than linear search.

Activity 3: Linear and binary search runtime.

Answer the following questions assuming each comparison takes 1 µs.

  1. Given a list of 1024 elements, what is the runtime for linear search if the search key is less than all elements in the list?
  2. Given a list of 1024 elements, what is the runtime for binary search if the search key is less than all elements in the list?