# LeetCode 35: Search Insert Position

## Problem Restatement

We are given a sorted array of distinct integers `nums` and an integer `target`.

If `target` exists in `nums`, return its index.

If `target` does not exist, return the index where it should be inserted so that the array remains sorted.

The required runtime is `O(log n)`, so the intended solution is binary search. The constraints say `nums` is sorted in ascending order and contains distinct values.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A sorted integer array `nums` and an integer `target` |
| Output | Index of `target`, or its insertion index |
| Array values | Distinct integers |
| Required runtime | `O(log n)` |
| Constraint | `1 <= nums.length <= 10^4` |

Function shape:

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

## Examples

Example 1:

```python
nums = [1, 3, 5, 6]
target = 5
```

The value `5` appears at index `2`.

Return:

```python
2
```

Example 2:

```python
nums = [1, 3, 5, 6]
target = 2
```

The value `2` does not appear.

To keep the array sorted, it should be inserted between `1` and `3`.

Return:

```python
1
```

Example 3:

```python
nums = [1, 3, 5, 6]
target = 7
```

The value `7` is greater than every number in the array.

It should be inserted at the end.

Return:

```python
4
```

## First Thought: Linear Search

The simplest approach is to scan from left to right.

The first index where `nums[i] >= target` is the answer.

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

        return len(nums)
```

This works because the array is sorted.

If we find a number equal to `target`, its index is the answer.

If we find a number greater than `target`, then `target` should be inserted before it.

If no such number exists, `target` belongs at the end.

## Problem With Linear Search

Linear search takes `O(n)` time.

The problem requires `O(log n)` time. Since the array is sorted, binary search can find the same boundary faster.

We want the first index where:

```python
nums[i] >= target
```

This is also called the lower bound of `target`.

## Key Insight

The answer is a boundary.

For every index before the answer:

```python
nums[i] < target
```

For the answer index and every index after it:

```python
nums[i] >= target
```

So we can binary search for the first position where `nums[i] >= target`.

Use a half-open interval:

```python
[left, right)
```

Start with:

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

This lets the answer be `len(nums)` when `target` is larger than every element.

## Algorithm

Initialize:

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

While `left < right`:

1. Compute `mid`.
2. If `nums[mid] >= target`, the answer is at `mid` or to its left, so set `right = mid`.
3. Otherwise, `nums[mid] < target`, so the answer is to the right, and set `left = mid + 1`.

When the loop ends, `left == right`.

Return `left`.

## Correctness

The algorithm maintains a search interval `[left, right)` that always contains the insertion position.

If `nums[mid] >= target`, then `mid` is a valid insertion candidate because placing `target` at or before `mid` can preserve sorted order. The first valid position may be `mid` or earlier, so keeping the left half is correct.

If `nums[mid] < target`, then `target` cannot be inserted at `mid` or before `mid` while preserving sorted order, because `nums[mid]` must remain before `target`. Therefore, the insertion position must be after `mid`.

Each step keeps the side that contains the first index where `nums[i] >= target`. When the interval becomes empty except for one boundary, `left` is exactly that index.

If `target` exists, this boundary is its index. If `target` does not exist, this boundary is where it should be inserted.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log n)` | Each step halves the search interval |
| Space | `O(1)` | We only use index variables |

## Implementation

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

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

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

        return left
```

## Code Explanation

We search the half-open interval `[left, right)`.

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

Using `right = len(nums)` is useful because the insertion position can be after the last element.

The loop continues while there is still more than one possible boundary.

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

The midpoint is:

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

If `nums[mid]` is greater than or equal to `target`, then `mid` may be the answer.

```python
if nums[mid] >= target:
    right = mid
```

Otherwise, `nums[mid]` is too small, so the answer must be after `mid`.

```python
else:
    left = mid + 1
```

At the end, `left` is the first index where `target` can be placed.

```python
return left
```

## Testing

```python
def check(nums: list[int], target: int, expected: int) -> None:
    actual = Solution().searchInsert(nums, target)
    assert actual == expected, (nums, target, actual, expected)

def run_tests():
    check([1, 3, 5, 6], 5, 2)
    check([1, 3, 5, 6], 2, 1)
    check([1, 3, 5, 6], 7, 4)
    check([1, 3, 5, 6], 0, 0)
    check([1], 1, 0)
    check([1], 0, 0)
    check([1], 2, 1)
    check([-10, -3, 0, 4, 9], -3, 1)
    check([-10, -3, 0, 4, 9], 5, 4)

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1,3,5,6]`, target `5` | Target exists |
| `[1,3,5,6]`, target `2` | Insert in the middle |
| `[1,3,5,6]`, target `7` | Insert at the end |
| `[1,3,5,6]`, target `0` | Insert at the beginning |
| `[1]`, target `1` | Single element found |
| `[1]`, target `0` | Single element insert before |
| `[1]`, target `2` | Single element insert after |
| Negative values | Confirms ordinary sorted order works |