# Binary search & boundary cases

Code With Purpose · English · Free starter lesson

## Concept

Binary search works on sorted data. Compare the middle element with the target, then discard the half that cannot contain it. Repeating this reduces the number of candidate positions by about half each step.

Here, low and high are inclusive bounds. While low <= high, the target—if present—is within that interval. Setting low = middle + 1 or high = middle - 1 excludes a checked position and guarantees progress. Returning -1 signals that no match was found.

For an indexable sequence, search takes O(log n) comparisons and O(1) extra space in this iterative version. Sorting unsorted data first has a separate cost. With repeated values this algorithm returns some matching index, not necessarily the first. Test empty inputs, endpoints, absent targets, and duplicates.

## Example

```python
def binary_search(values, target):
    low, high = 0, len(values) - 1
    while low <= high:
        middle = (low + high) // 2
        if values[middle] == target:
            return middle
        if values[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return -1

print(binary_search([2, 5, 8, 12, 19], 12))
print(binary_search([], 12))
```

## Expected output

```text
3
-1
```

## Exercise

Test the first and last elements and a missing target. Can you call this function directly on [8, 2, 5]? Explain.

## Suggested solution

```
assert binary_search([2, 5, 8], 2) == 0
assert binary_search([2, 5, 8], 8) == 2
assert binary_search([2, 5, 8], 6) == -1
# [8, 2, 5] is unsorted: the algorithm's assumption is broken.
# Sort first if appropriate, noting that indices then refer to the sorted list.
```

## Takeaway

An algorithm is correct only when its assumptions hold.

Reference: https://docs.python.org/3/library/bisect.html

https://codewithpurposeai.in/lesson-dsa-binary-search.html?lang=english