Binary search is an efficient algorithm for finding values in a sorted data-set.
Let’s implement this algorithm in Python!
Here’s a recap of the algorithm:
Check the middle value of the dataset.
- If this value matches our target we return the target value index.
If the middle value is greater than our target
- Begin at step 1 using the left half of the list.
If the middle value is less than our target
- Begin at step 1 using the right half of the list.
As an added challenge, we are going to use a recursive approach. When using recursion, we always want to think of the problem in two ways: the base case and the recursive step.
We have two base cases for this algorithm:
- We found the value and return its index
- We didn’t find the value because the list is empty!
In order to reach the base case of an empty list, we’ll need to remove an element at each recursive call…
binary_search() which has two parameters:
Our first base case is when the sorted list is empty.
binary_search(), use a conditional to check whether the list is empty.
If it is, return
"value not found".
We’ll set up our recursive step.
Declare two variables:
mid_idx should be the middle index of
mid_val is the value located in
sorted_list at the
return these two variables like so:
return mid_idx, mid_val