Congratulations, you implemented a version of the binary search algorithm using recursion!
Let’s recap how we solved this problem:
- We know our inputs will be sorted, which helps us make assertions about where to search for values.
- We divide the list in half and compare our target value with the middle element.
- If they match, we return the index
- If they don’t match, we begin again at the first step with the appropriate half of the original list.
- When the list is empty, the target is not found.
Our original solution solved the problem of reducing the sorted input list by making a smaller copy of the list.
This is wasteful! At each recursive call we’re copying N/2
elements where N
is the length of the sorted list.
We can do better by using pointers instead of copying the list. Pointers are indices stored in a variable that mark the beginning and end of a list:
vehicles = ["car", "jet", "camel", "boat"] start_of_list = 0 end_of_list = len(vehicles) # 4 vehicles[start_of_list : end_of_list] # ["car", "jet", "camel", "boat"] middle_of_list = len(vehicles) // 2 # 2 vehicles[start_of_list : middle_of_list] # ["car", "jet"] vehicles[middle_of_list : end_of_list] # ["camel", "boat"] # This example copies the list to show what portion is covered # We won't need to copy in the algorithm!
With pointers, we’ll track which sub-list we’re searching within the original input and there’s no need for copying.
Our overall strategy is the same, but we’ll need to change the following sections:
binary_search()
has two parameters- It should have four
- Our base case checks for an empty list
- It should check whether the pointers indicate an empty sub-list
- Our recursive calls use copied sub-lists
- They should update the pointers to indicate which portion of the list we’re searching.
- Our “right-half” recursive calls do some arithmetic.
- That’s no longer necessary!
Instructions
Run the new version of binary_search()
which uses pointers instead of copying lists.