> For the complete documentation index, see [llms.txt](https://leetcode.realtemirov.uz/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode.realtemirov.uz/problems/35.-search-insert-position.md).

# 35. Search Insert Position

🟩 Easy

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with `O(log n)` runtime complexity.

## Example 1

> **Input**: nums = \[1,3,5,6], target = 5\
> **Output**: 2

## Example 2

> **Input**: nums = \[1,3,5,6], target = 2\
> **Output**: 1

## Example 3

> **Input**: nums = \[1,3,5,6], target = 7\
> **Output**: 4

## Constraints

* `1 <= nums.length <= 10^4`
* `-10^4 <= nums[i] <= 10^4`
* `nums` contains **distinct** values sorted in **ascending** order.
* `-10^4 <= target <= 10^4`

## Solution

My Solution

```go
func searchInsert(nums []int, target int) int {
    l, r := 0, len(nums)-1

    for l <= r {
        mid := l + (r-l)/2
        if nums[mid] < target {
            l = mid + 1
        } else {
            r = mid - 1
        }
    }

    return l
}
```

### Approach

This solution uses a modified binary search to find the insertion position:

1. Binary Search Implementation:
   * Uses standard binary search framework
   * When element is found, that's the insertion position
   * When element is not found, 'l' will be at the correct insertion position
2. Key Insights:
   * The left pointer 'l' always ends up at the correct insertion position
   * No need for special handling of not-found cases
   * Works for both existing and non-existing targets

### Complexity Analysis

#### Time Complexity: O(log n)

* Uses standard binary search
* Search space is halved in each iteration
* Takes at most log₂(n) steps to find position

#### Space Complexity: O(1)

* Only uses constant extra space:
  * Two pointers (left, right)
  * Mid index variable

### Why it works

* When target exists:
  * Binary search finds exact position
  * Left pointer stops at target's index
* When target doesn't exist:
  * Left pointer stops at first element greater than target
  * This is exactly where target should be inserted
  * Right pointer will be at left - 1
* Edge cases handled naturally:
  * Target smaller than all elements: left = 0
  * Target larger than all elements: left = len(nums)

![result](https://600345290-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FrSK2xH3txU3tYyDsT8mQ%2Fuploads%2Fgit-blob-51c7fba3e132d270d0cdc90676a0865fe0d07b5c%2F35.png?alt=media)

Leetcode: [link](https://leetcode.com/problems/search-insert-position/description/)