Congratulations, you implemented a version of the binary search algorithm using recursion!
Let’s recap how we solved this problem:
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
Run the new version of
binary_search() which uses pointers instead of copying lists.