Implement the binary search algorithm using both recursion and iteration. You'll refactor to improve the algorithm's efficiency as well!

Binary Search: Python

We now have a base case for when we do not find the value in our sorted list, but we need a base case for when we DO find the value.

At this step, we have three options:

* **BASE CASE:** `mid_val` matches our `target`
* **RECURSIVE STEP:** `mid_val` is less than our target
* **RECURSIVE STEP:** `mid_val` is more than our target

We'll tackle the alternate base case first.

Recursive Binary Search: Base Case 2

Anything recursive can be written iteratively. 

As a final exercise, we'll implement the binary search algorithm using iteration.

Our strategy remains largely the same as the recursive approach which used pointers. 

Instead of recursive calls, we'll substitute a `while` loop.

Iterative Binary Search

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...

Recursive Binary Search: Base Case

Congratulations, you implemented a version of the binary search algorithm using recursion!

Let's recap how we solved this problem:

1. We know our inputs will be sorted, which helps us make assertions about where to search for values.
2. We divide the list in half and compare our target value with the middle element.
3. If they match, we return the index
4. If they don't match, we begin again at the first step with the appropriate half of the original list.
5. 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:

```py
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!

Recursive Binary Search: Review and Refactor

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`:

```py
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]
```



