# Binary search

Binary search is a fast and efficient search algorithm where an ordered and sorted input is recursively bisected (with the “bad” half discarded) until the result of the search remains.

## Efficiency

Binary search is `O(log n)`

(logarithmic time/space) in Big O notation. Given `n`

elements in the input, completing the search will take (at most) `log2 * n`

steps. So, given `8`

elements, the search will take (at most) `3`

steps.

## Requirements

- Input must be ordered and sorted

## Implementation

Pseudocode:

```
list = ordered_and_sorted_list
low = 0
high = list.length - 1
match = what_i_want
while low <= high
mid = (low + high) / 2
if mid == match: return mid
if mid > match: high = mid - 1
if mid < match: low = mid + 1
```

Python (recursive):

```
def binary_search(arr, low, high, match):
mid = (high + low) // 2
if arr[mid] == match:
return mid
elif arr[mid] > match:
return binary_search(arr, low, mid - 1, match)
else:
return binary_search(arr, mid + 1, high, match)
# Test
arr = [1, 3, 4, 7, 11]
low = 0
high = len(arr) - 1
match = 7
result = binary_search(arr, low, high, match)
```