With both of our base cases covered, we’ll turn our attention to the recursive step.
We have two options depending on the comparison of mid_val
to target
.
You’ll recall that our data-set is sorted.
We’ll leverage that knowledge in our recursive step to cut the problem in half at each step.
If the mid_val
is greater than our target
, we know we can disregard every element at an index greater than mid_idx
:
sorted_list = [9, 10, 11, 12, 13] target = 9 mid_idx = len(sorted_list) // 2 # 2 mid_val = sorted_list[mid_idx] # 11 11 > 9 # True # No need to check right half: [12, 13] # Those values will only be bigger... # Instead, we'll check the left half! left_half = sorted_list[:mid_idx] # [9, 10] # If mid_val had been less than the target # We would check in the right half... target = 17 17 > mid_val right_half = sorted_list[mid_idx + 1:] # [12, 13]
Instructions
Below our check for whether mid_val == target
make a new conditional.
Check whether the middle value is greater than the target.
If it is:
- make a variable:
left_half
that is every element insorted_list
up to but not includingmid_val
. - return a recursive call to
binary_search()
givenleft_half
andtarget
as arguments.
Make another conditional below the last checking if mid_val
is less than our target
.
If it is:
- make a variable:
right_half
that is every element insorted_list
aftermid_val
. - make a variable:
result
and assign it to a recursive call ofbinary_search()
givenright_half
andtarget
.
Why are we storing this in a variable?
We’re making a smaller copy of the sorted list at each recursive call, so our indices for the same values change:
sorted_list = [7, 8, 9, 10, 11] right_half = [10, 11] # index of "11" in sorted_list: 4 # index of "11" in right_half: 1
We can account for the missing indices by returning the result
plus the index segments of the lists we’ve discarded.
We’ll do this in the form of mid_idx + 1
.
sorted_list = [7, 8, 9, 10, 11] binary_search(sorted_list, 11) mid_idx = 2 # 9 < 11, we search in right half... # within the recursive call: # right_half = [10, 11] # mid_idx = 1 # target matched, we return 1 # within original call, result is 1 (result + mid_idx + 1) == 4
Return result
plus the missing indices.
When we search in the right half of the list and find the value, this works.
Unfortunately, there’s an error if we can’t locate the value: We’ll try to add "value not found"
to mid_idx + 1
, resulting in a TypeError
.
Add in a conditional:
- If
result
is"value not found"
- then return
result
.
- then return
Otherwise, return the index arithmetic as before.