2.3 Python: Linear and binary search

Linear search

Search algorithms are used to find the location (index) of some key element in a list, or otherwise indicate that the key is not in the list. Linear search is a search algorithm that starts from the beginning of a list, and checks each element until the search key is found or the end of the list is reached. The linear_search() function shown below compares each item in a given list, one at a time.

The figure below shows the linear search code. If the key value is found, the index is returned. If the key value is not found, -1 is returned.

Linear search algorithm

Anagram Checker
NUMBERS: [2, 4, 7, 10, 11, 32, 45, 87] 
Enter an integer value: 10
Found 10 at index 3.
...
NUMBERS: [2, 4, 7, 10, 11, 32, 45, 87]  
Enter an integer value: 17
17 was not found.

Activity 1: Linear search algorithm.

How many comparisons are performed by linear_search() for each example?

  1. List: [12, 75, 18, 22, 94, 16, 22] | Key: 94
  2. List: [12, 75, 18, 22, 94, 16, 22] | Key: 22
  3. List: [12, 75, 18, 22, 94, 16, 22] | Key: 10

Binary search

The binary search algorithm also finds the location of a key value in a list, but is much faster than linear search because the search is performed on a sorted list. Binary search compares the middle element of the list to the key. If the middle element matches the key, then the algorithm is complete and returns the index. If the middle element is smaller than the key, the loop proceeds by searching the first half of the list. If the middle element is larger than the key, the loop proceeds by searching the last half of the list. In this way the search field is always cut in half, leading to many fewer comparisons.

To calculate the index in the middle of low and high indices, the sum of high and low is divided by 2. If the result is not an integer, the value is rounded down to a whole number using floor division. Python has a special floor division operator, //, that automatically drops the quotient's decimal portion, so this operator is used when calculating the middle index: mid = (high + low) // 2.

Binary search algorithm

Anagram Checker
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.

How many list items are compared to the key by binary_search() for each example?

  1. List: [12, 18, 22, 34, 41, 74, 88] | Key: 74
  2. List: [12, 18, 22, 34, 41, 74, 88] | Key: 10

Linear and binary search algorithms.

Both linear and binary search algorithms appear in the IDE below. The functions are modified to count the total number of comparisons each algorithm performs. The main program calls both search algorithms and the total number of comparisons each algorithm performs is displayed as part of the output. Try different lists and key values.

Input
45

Output
NUMBERS: [2, 4, 7, 10, 11, 32, 45, 87]
Enter an integer key to search for: 
Linear search: Found 45 at index 6 with 7 comparisons.
Binary search: Found 45 at index 6 with 3 comparisons.