Binary search is a [[divide-and-conquer]] algorithm to find an element in a list.
```python
def binary_search_helper(lst, ele, left, right):
if left > right:
return None
else:
mid = (left + right) // 2
if lst[mid] == elt:
return mid
elif lst[mid] < elt:
binary_search(lst, ele, mid+1, right)
elif lst[mid] > elt:
binary_search(lst, ele, left, mid-1)
# for a list in ascending order
def binary_search_asc(lst, ele):
binary_search_helper(lst, ele, 0, size(lst) - 1)
```
## binary search correctness
To prove the correctness of binary search, we can use a [[loop invariant]] proof. The loop invariant of binary search states that
> If the element is in the entire list, it will be in the search region, bounded by `left` and `right` inclusively.
In the base case, or the initialization, `left` and `right` point to both ends of the list, and so it must be true that if the element is in the list it is between the two ends.
In the next iteration, if the midpoint is not the element, then there are two cases:
- If the element is greater than the midpoint, `left` is updated to be one element to the right of the midpoint.
- If the midpoint is less than the element, `right` is updated to be one element to the left of the midpoint.
In either case, the new left or right is set such that if the element is in the list it must be between the new left and right.
Finally, we can show that the loop will terminate either when the element is the midpoint, returning the correct output, or when the indices of `right < left`, which means the search region is empty and the correct response is `None`.
## binary search running time
Intuitively, we know that binary search halves the search region with each iteration. In the worst case, the element to find is not in the list. If we consider an input with $2^k$ elements, the worst case will require at most $k+1$ steps where $k = \log_2 \ n$. In asymptotic notation, we can say $O(\log_2 \ n)$ and in fact, with a bit more work, we could show that binary search is $\Theta (\log_2 \ n)$.
## Python implementation
The implementation of binary search in [[Python]] is
```python
def binary_search_helper(arr, target, left, right):
# Base case: if the range is invalid
if left > right:
return -1 # target is not found in the list
mid = (left + right) // 2
# Check if the middle element is the target
if arr[mid] == target:
return mid
# If the target is smaller than the mid element, it must be in the left subarray
elif arr[mid] > target:
return binary_search_helper(arr, target, left, mid - 1)
# If the target is larger than the mid element, it must be in the right subarray
else:
return binary_search_helper(arr, target, mid + 1, right)
# Helper function to call the recursive function with initial parameters
def binary_search(arr, target):
return binary_search_recursive(arr, target, 0, len(arr) - 1)
```
#rough