Programs may need to find a specific value within a list. For example, given a list with the values [5, 20, 15, 10], a program may be asked to identify (by index number) where a specific value is located within the list. In this example, the value 15 is located at index 2, the value 20 is located at index 1, and the value 12 is not found within the list at all.
It's easy for humans to review a small list and find a target value. Computer programs can also carefully search the list to try and find the values. In this lesson, you are going to learn two common ways to programmatically search a list.
Sequential Search
Let's consider a list with the following values: [ 15, 9, 1, 14, 12, 8, 10, 6, 5, 3 ]. The data is unsorted (not arranged in sequential, numeric order). A search algorithm will want to identify the element (by index) where a target value is stored.
A sequential search or linear search works on unsorted data. You simply start at the beginning of your list and compare every value, one by one, until you have found the target element. If you reach the end of the data without finding your target value, then the algorithm should note that the value was not found.
Sequential SearchIf we are searching for an element holding the number 10, we would set up a loop from the beginning to the end of the list. At each element, compare the value in the element to 10. If there is a match, halt the loop immediately and print the index of the element where the 10 was found. Otherwise, continue the loop to examine the next element. In our example list, 10 is found at index 6, so the algorithm would identify 6 as the result.
As you can see, it took seven steps to compare every value from the beginning until we found the "10" at index 6. The average time it takes to find the value you're looking for depends directly on how many elements "N" are in your data set. With 10,000 elements in an unsorted array, you might get lucky and find your target value early, or you might have to iterate through the entire array. As "N" increases, the time it takes a sequential search to find a target value will, on average, increase linearly.
Remember, in Python, you can use a "for" loop and the "range" keyword to loop with index values over a range. Each element in a list has an index from 0 up to the length minus 1, and we can find the length of a list with the len() function. The following pattern shows how to set up a "for" loop that will use a numeric index to iterate over a list and process each element.
myNumbers = [15, 9, 1, 14, 12, 8, 10, 6, 5, 3]
length = len(myNumbers) # number of elements in list
# iterate over the myNumbers list from 0 to length-1
for i in range(0,length):
# loop body here; access current element with myNumbers[i]
Copy
The Python program below sets up an initial list, asks the user for a target value, and then runs a sequential search on the list to find the value. Run the program a few times to see the sequential search in action.
Try It Now
If the target value is found, the loop will print that value and the location (index) where the value was found. The "break" keyword halts the loop immediately and causes the "else" block to be skipped.
Enter target value: 14
14 found at location 3
When the target is not found, the loop completes normally, and the "else" logic will display a "not found" message.
Enter target value: 11
11 not found
Binary Search
A binary search is a popular and efficient search algorithm that works very quickly if your data is sorted in numeric order. Let's sort our example list so the numbers are in increasing order: [1, 3, 5, 6, 8, 9, 10, 12, 14, 15]. How can we take advantage of the sorted data to search more efficiently?
Sorted Data
The binary search will start by looking at the element in the middle of the list. If the value there is higher than the target, then you can eliminate all of the elements to the right and only consider the remaining elements to the left. If the value in the middle is lower than the target, then you can eliminate all the elements to the left. Whichever half you choose, again sub-divide that smaller list and look at the value in the middle. Continue eliminating half of the remaining list until you land on your target value or run out of elements to compare. Because you can discard half of the remaining options on each pass, the binary search is very efficient!
Binary Search process diagramLet's try and find the value "10" in our sorted list using a binary search. There are 10 elements in the list, so the low index is 0 and the high index is 9. We will adjust these "low" and "high" index values on each pass as we eliminate half of the elements.
We begin each pass by calculating a middle index as the midpoint between the current low and high indexes.
middleIndex = (highIndex + lowIndex) /2
On the first pass, our low index is 0 and the high index is 9, so (0 + 9) / 2 is 4.5, and values to the right of the decimal point are truncated by Python when doing integer math. So, our mid-point in the first pass is index 4. The value at index 4 is "8", which is less than our "10" target so that index and all elements to the left can be ignored.
To discard all elements to the left of the current midpoint, we set the low index equal to the midpoint + 1.
lowIndex = middleIndex + 1
The new low index is 4 + 1 = 5. Now that we have discarded half of the elements, it's time for the second pass. We again calculate the midpoint between the current low (5) and high (9) index values. (9 + 5) / 2 = 7. The value at index 7 is "12" which is too high, so we can eliminate that element and all others to the right. This means we move the high index down below the midpoint.
highIndex = middleIndex - 1
The new high index is 7 - 1= 6. On the third pass, our low index is 5 and our high index is 6. There are only two elements remaining! Our middle index formula tells us to look at (6 + 5) / 2 = 5. The value at index 5 is "9" which is too low, so we adjust our low index to 5 + 1 = 6.
On the fourth pass, our low index and high index are both 6, and the midpoint would also be calculated as (6 + 6) / 2 = 6. Checking the value at element 6, we find our target "10", so the algorithm can display the index 6 as the final result. As you can see, it only took 4 steps to search a 10-element list!
What happens if the value is not in the list? Running an additional pass will cause your lower index value to become greater than the higher index. This is your signal that the target value is not found, and you can halt the algorithm with a message that the target value was not found.
The binary search is much more efficient than the sequential search for sorted lists with many elements. We get this efficiency because we can toss out half of the remaining elements at each step in the search process. The efficiency is logarithmic with respect to the number of elements "N", calculated as log2(N) + 1. The binary search could fully scan an array with 10,000 elements in only 14 passes!
Binary Search - Maximum Iterations
What is the maximum number of iterations a binary search algorithm will take to find a target value? This is reasonably easy to calculate given some number of elements "N" in the list. You simply need to divide the number of elements "N" by 2 repeatedly until you only have 1 element left.
Consider a list with 400 elements. How many elements will each loop iteration consider as part of the binary search?
First Pass - Binary search operates on 400 elements
Second Pass - Binary search operates on 200 elements
Third Pass - Binary search operates on 100 elements
Fourth Pass - Binary search operates on 50 elements
Fifth Pass - Binary search operates on 25 elements
Sixth Pass - Binary search operates on 13 elements
Seventh Pass - Binary search operates on 7 elements
Eighth Pass - Binary search operates on 4 elements
Ninth Pass - Binary search operates on 2 elements
Tenth Pass - Binary search operates on 1 element
Therefore, to fully search a 400-element list, a binary search algorithm would only need about 10 iterations. Notice that, when dividing the number of elements by 2, we simply rounded "up" each time a decimal result like 12.5 was obtained.
On your own, can you calculate the maximum number of iterations a binary search would take for lists of 50 and 200 elements?
1. Does the data have to be sorted for a sequential search to work?
2. How does the main loop in a sequential search work?
3. What happens in a sequential search when the target value is not found?
4. When searching "N" elements, what is the worst-case number of iterations in the sequential search?
5. What type of efficiency (linear, logarithmic, quadric) does the sequential search have?
6. Does the data have to be sorted for a binary search to work?
7. How do you calculate the midpoint on each pass through the binary search?
8. In a binary search, how do you adjust the low index if the midpoint is too low?
9. In a binary search, how do you adjust the high index if the midpoint is too high?
10. What type of efficiency (linear, logarithmic, quadric) does the binary search have?
11. How can you calculate the maximum number of iterations a binary search might take to find a target value?
1. No, the data does not have to be sorted for a sequential search to work. It can work on unsorted data as well.
2. In a sequential search, the main loop iterates through each element of the list and compares it to the target value until the target value is found or the end of the list is reached.
3. If the target value is not found in a sequential search, the algorithm will continue iterating through the entire list and then note that the value was not found.
4. In the worst case scenario, the sequential search would iterate through all "N" elements in the list to find the target value.
5. The sequential search has linear efficiency, meaning that the time it takes to find a target value increases linearly with the number of elements in the list.
6. Yes, the data must be sorted for a binary search to work efficiently.
7. In a binary search, the midpoint is calculated by adding the low index and high index and then dividing by 2.
8. If the midpoint in a binary search is too low, the low index is adjusted to be equal to the midpoint index plus 1.
9. If the midpoint in a binary search is too high, the high index is adjusted to be equal to the midpoint index minus 1.
10. The binary search has logarithmic efficiency, meaning that the time it takes to find a target value increases logarithmically with the number of elements in the sorted list.
11. The maximum number of iterations a binary search might take to find a target value can be calculated by repeatedly dividing the number of elements "N" by 2 until only 1 element is left. The number of divisions is the maximum number of iterations.