Binary Search

Question

Given a strictly increasing array of integers and a target, return the target's index or `-1` when it is absent.

```python
def binary_search(nums: list[int], target: int) -> int: ...
```

The solution must run in `O(log n)` time and use `O(1)` auxiliary space. An empty array returns `-1`.

## Staged follow-ups

1. Return the first position where the target could be inserted while preserving order.
2. Support duplicate values by returning the first matching index.
3. Search a conceptually unbounded sorted data source through a bounded-access interface.