# Binary Search — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/binary-search

> Halve a sorted range each step to find a target in O(log n).

## Discard half every step

On a **sorted** array, compare the target to the middle element. If the target is larger, the whole left half (including mid) is irrelevant — move `left` past it. Otherwise drop the right half. Each step halves the search space: `O(log n)`.

## Iterative template

Use `left <= right` and `mid = left + (right-left)//2` to avoid overflow in other languages.

```python
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1     # target in right half
        else:
            hi = mid - 1     # target in left half
    return -1
```

Output:

```
binary_search([10,20,30,40,50,60,70,80], 60) -> 5
```

## Dry run: find 60

`[10 20 30 40 50 60 70 80]`

- Step 1: lo=0 hi=7 mid=3 → arr[3]=40 < 60 → lo=4
- Step 2: lo=4 hi=7 mid=5 → arr[5]=60 → **found at index 5**

**Quiz:** Binary search requires the data to be...

- [x] Sorted (or monotonic on the predicate)
- [ ] Stored in a hash map
- [ ] Of prime length

*Answer:* Sorted (or monotonic on the predicate). Discarding half only works if one side is guaranteed to not contain the target — that needs order.