# 35 Search Insert Position

## 1. Description

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.

Constraints:

- \(1 \leq nums.length \leq 10^{4}\)
- \(-10^{4} \leq nums[i] \leq 10^{4}\)
`nums`

contains**distinct**values sorted in**ascending**order- \(-10^{4} \leq target \leq 10^{4}\)

### 1.1. Examples:

Input: nums = [1,3,5,6], target = 5 Output: 2 Input: nums = [1,3,5,6], target = 2 Output: 1 Input: nums = [1,3,5,6], target = 7 Output: 4

## 2. Solution

### 2.1. Understanding the problem

How do we know that this is a Binary Search problem? Two points:

- it requires
`O(log n)`

time complexity, but this is not the deciding factor. - The task asks us to find a certain
*index/position*by comparing a*target element*with an ordered list of elements.- It could be asking inexplicitly but you need to be able to figure out what is really being asked.

### 2.2. Algorithm

### 2.3. Code

def searchInsert(nums, target): """ :type nums: List[int] :type target: int :rtype: int """ left_idx = 0 right_idx = len(nums) - 1 while left_idx <= right_idx: mid = left_idx + (right_idx - left_idx) // 2 curr = nums[mid] if curr == target: return mid elif curr > target: right_idx = mid - 1 else: left_idx = mid + 1 # [1, target, curr] # right_idx, left_idx, left_idx+1 # [curr, target, 4] # right_idx, left_idx, left_idx+1 return left_idx # tests nums, target, result = [0], 0, 0 print(searchInsert(nums, target) == result) nums, target, result = [0], 1, 1 print(searchInsert(nums, target) == result) nums, target, result = [0], -1, 0 print(searchInsert(nums, target) == result) nums, target, result = [0, 2], 1, 1 print(searchInsert(nums, target) == result) nums, target, result = [0, 2, 3], 0, 0 print(searchInsert(nums, target) == result) nums, target, result = [0, 2, 3], 4, 3 print(searchInsert(nums, target) == result)

True True True True True True

#### 2.3.1. Complexity

##### 2.3.1.1. Time complexity:

`O(log n)`

##### 2.3.1.2. Space complexity:

`O(1)`

### 2.4. Leetcode solution

`nil`

but basically the same implementation.

```
<<imports for typing>>
```

#### 2.4.1. Time complexity:

#### 2.4.2. Space complexity:

## 3. More analysis

### 3.1. General thoughts

Again we know we need to use Binary Search, but the implementation details suck.

Basically we need to under stand what it means to *insert* an element to the list at position `idx`

.
A trivial case is that we can find `target`

in the list, then we return `mid`

.

We now consider when we can't find `target`

in the list and what should we return in the end.
First of all, we can easily tell that in this case, the terminating condition for the binary search would be `left_idx == right_idx + 1`

.

By actually inserting `target`

into the list, we then will have something like below:

curr | target | n |

right_idx | left_idx | left_idx + 1 |

n | target | curr |

right_idx | left_idx | left_idx + 1 |

We can see from the insertion tables that `target`

is always inserted at the `left_idx`

location.

### 3.2. Related problems

- 278 First Bad Version
- 704 Binary Search
- [BROKEN LINK: 6705fa69-9835-4076-b293-cd962e3c5828]