# 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)
``````