# LeetCode 704: Binary Search

## Problem Restatement

We are given an array of integers `nums`.

The array is sorted in ascending order.

We are also given an integer `target`.

We need to find `target` in `nums`.

If `target` exists, return its index.

If `target` does not exist, return:

```python
-1
```

The required runtime is `O(log n)`, so we should use binary search instead of scanning the array one element at a time.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A sorted integer array `nums` |
| Input | An integer `target` |
| Output | The index of `target`, or `-1` if missing |
| Required complexity | `O(log n)` time |
| Array order | Ascending |

The function shape is:

```python
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        ...
```

## Examples

Example 1:

```python
nums = [-1, 0, 3, 5, 9, 12]
target = 9
```

The value `9` appears at index `4`.

So the answer is:

```python
4
```

Example 2:

```python
nums = [-1, 0, 3, 5, 9, 12]
target = 2
```

The value `2` does not appear in the array.

So the answer is:

```python
-1
```

## First Thought: Linear Search

The simplest solution is to check every element from left to right.

```python
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        for i, num in enumerate(nums):
            if num == target:
                return i

        return -1
```

This is correct, but it does not satisfy the required runtime.

If the array has `n` elements, linear search can take:

```python
O(n)
```

The problem asks for `O(log n)`, so we need to use the sorted order.

## Key Insight

Because the array is sorted, we can discard half of the remaining search space after each comparison.

Pick the middle index.

If the middle value equals `target`, we are done.

If the middle value is smaller than `target`, then every value on the left side is also too small. We only need to search the right half.

If the middle value is larger than `target`, then every value on the right side is also too large. We only need to search the left half.

This is binary search.

## Algorithm

Use two pointers:

```python
left = 0
right = len(nums) - 1
```

These pointers describe the current search range.

While `left <= right`:

1. Compute the middle index.
2. Compare `nums[mid]` with `target`.
3. If they are equal, return `mid`.
4. If `nums[mid] < target`, move `left` to `mid + 1`.
5. If `nums[mid] > target`, move `right` to `mid - 1`.

If the loop ends, the target is not in the array.

Return `-1`.

## Correctness

At the start, the search range is the entire array.

During each iteration, the algorithm chooses the middle index `mid`.

If `nums[mid] == target`, returning `mid` is correct.

If `nums[mid] < target`, then every index from `left` through `mid` contains a value less than or equal to `nums[mid]`, because the array is sorted. Therefore none of those values can be `target`. Removing them from the search range is safe.

If `nums[mid] > target`, then every index from `mid` through `right` contains a value greater than or equal to `nums[mid]`. Therefore none of those values can be `target`. Removing them from the search range is safe.

So after every step, if `target` exists, it remains inside the current search range.

When the range becomes empty, there is no possible index left where `target` can appear. Returning `-1` is correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log n)` | Each step cuts the search range roughly in half |
| Space | `O(1)` | Only a few integer variables are used |

## Implementation

```python
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2

            if nums[mid] == target:
                return mid

            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return -1
```

## Code Explanation

We begin with the full array as the search range:

```python
left = 0
right = len(nums) - 1
```

The loop continues while the range is valid:

```python
while left <= right:
```

The middle index is:

```python
mid = left + (right - left) // 2
```

This form avoids overflow in languages with fixed-size integers. In Python, overflow is not a practical issue, but this version is still a good habit.

If the middle value is the target, return the index:

```python
if nums[mid] == target:
    return mid
```

If the middle value is too small, the target can only be on the right:

```python
if nums[mid] < target:
    left = mid + 1
```

Otherwise, the middle value is too large, so the target can only be on the left:

```python
else:
    right = mid - 1
```

If the loop finishes, the target was not found:

```python
return -1
```

## Testing

```python
def test_search():
    s = Solution()

    assert s.search([-1, 0, 3, 5, 9, 12], 9) == 4
    assert s.search([-1, 0, 3, 5, 9, 12], 2) == -1
    assert s.search([5], 5) == 0
    assert s.search([5], -5) == -1
    assert s.search([1, 2, 3, 4, 5], 1) == 0
    assert s.search([1, 2, 3, 4, 5], 5) == 4
    assert s.search([-10, -3, 0, 7, 11], -3) == 1

    print("all tests passed")

test_search()
```

Test coverage:

| Test | Why |
|---|---|
| Target exists in middle | Confirms normal binary search |
| Target missing | Confirms `-1` result |
| Single element found | Confirms minimum input |
| Single element missing | Confirms empty search range after one step |
| Target at first index | Confirms left boundary |
| Target at last index | Confirms right boundary |
| Negative values | Confirms comparisons work across signs |