# Binary Search in Python

Binary search is a fast way to figure out if a certain element exists in a sorted list of elements. *Sorted* is a really important keyword here. **Binary search only works with sorted lists.**

There’s at least two approaches to implementing binary search: iterative and recursive.

I think the iterative approach is preferable in all cases because it has the same time complexity as the resursive approach while maintaining constant space complexity.

The recursive approach, on the other hand, needs to add log(n) frames to the stack in the worst case. It is simply unneccesary to consume any more than constant space with an iterative approach.

Both of the implementations below return the index of the target element. If the target element doesn’t exist, then -1 is returned.

### Iterative Approach

```
from math import floor
normal_input = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
empty_list_input = []
single_element_input = [7]
def iterative_binary_search(target, array):
ix_low = 0
ix_high = len(array) - 1
while ix_low <= ix_high:
ix_mid = floor((ix_low + ix_high) / 2)
mid_value = array[ix_mid]
if mid_value == target:
return ix_mid
if target > mid_value:
ix_low = ix_mid + 1
else:
ix_high = ix_mid - 1
return -1
assert iterative_binary_search(16, normal_input) == 15
assert iterative_binary_search(5, empty_list_input) == -1
assert iterative_binary_search(7, single_element_input) == 0
```

#### Time Complexity

`O(log(n))`

#### Explanation

Each time through the while loop the size of the remaining elements that we are searching through is reduced by half. Assuming 20 elements in the sorted array, the pool of candidate elements decreases like this:

- 20 / 2 = 10
- 10 / 2 = 5
- 5 / 2 = 2 (floor)
- 2 / 2 = 1

In the worst case the binary search takes 4 steps. The worst case is when the target element is the last element we look at. Note that n=20, and 4 is roughly equal to log2(20). log2(20) is ~4.32.

#### Space Complexity

`O(1)`

#### Explanation

Only 4 scalar variables are used: `ix_low`

, `ix_high`

, `ix_mid`

, and `mid_value`

. The size of the input array is `n`

, but that does not count towards the space complexity of the binary search implementation.

### Recursive Approach

```
def recursive_binary_search(target, array, ix_low, ix_high):
if ix_low > ix_high:
return -1
ix_mid = floor((ix_low + ix_high) / 2)
mid_value = array[ix_mid]
if mid_value == target:
return ix_mid
if target > mid_value:
return recursive_binary_search(target, array, ix_mid + 1, ix_high)
else:
return recursive_binary_search(target, array, ix_low, ix_mid - 1)
assert recursive_binary_search(16, normal_input, 0, len(normal_input) - 1) == 15
assert recursive_binary_search(5, empty_list_input, 0, len(empty_list_input) - 1) == -1
assert recursive_binary_search(7, single_element_input, 0, len(single_element_input) - 1) == 0
```

This solution looks similar to the iterative solution with two big differences:

- All relevant information (
`target`

,`array`

,`ix_low`

, and`ix_high`

) is passed to each recursive call to`recursive_binary_search`

.`ix_mid`

doesn’t need to be passed because it is derived from`ix_low`

and`ix_high`

every time. - Recursive calls are being made, which implies that base cases are defined to prevent infinite recursion

#### Time Complexity

`O(log(n))`

#### Explanation

See the explanation above for the time complexity of the iterative approach.

#### Space Complexity

`O(log(n))`

#### Explanation

There are log(n) recursive calls to `recursive_binary_search`

made in the worst case. Each of these recursive calls adds a frame to the stack, making the space complexity O(log(n)) based on the space consumed by the stack.