Learn
Binary Search: Python
Recursive Binary Search: Base Case

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…

### Instructions

1.

Define `binary_search()` which has two parameters: `sorted_list` and `target`.

Our first base case is when the sorted list is empty.

Within `binary_search()`, use a conditional to check whether the list is empty.

If it is, return `"value not found"`.

2.

We’ll set up our recursive step.

Declare two variables: `mid_idx` and `mid_val`.

`mid_idx` should be the middle index of `sorted_list`.

`mid_val` is the value located in `sorted_list` at the `mid_idx`.

return these two variables like so: `return mid_idx, mid_val`