---
# System prepended metadata

title: LC 35. Search Insert Position
tags: [easy, leedcode, Binary Search, python]

---

# LC 35. Search Insert Position

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

###### tags: `leedcode` `python` `easy` `Binary Search`

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 mustwrite an algorithm with<code>O(log n)</code> 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:** 

- <code>1 <= nums.length <= 10<sup>4</sup></code>
- <code>-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup></code>
- <code>nums</code> contains  **distinct**  values sorted in  **ascending**  order.
- <code>-10<sup>4</sup> <= target <= 10<sup>4</sup></code>

## Solution 1 - Binary Search
#### Python
```python=
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1

        return left
```
#### C++
```cpp=
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};
```

## Solution 2 - Binary Search
```python=
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)

        while left < right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid
            else:
                left = mid + 1

        return left
```

>### Complexity
>n = nums.length
>|             | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1  | O(logn)         | O(1)             |
>| Solution 2  | O(logn)         | O(1)             |


## Note
sol1, 2:
```python=
兩種sol主要差在以下3點
1. 
sol1: left, right = 0, len(nums) - 1
sol2: left, right = 0, len(nums)

2.
sol1: while left <= right:
sol2: while left < right:

3.
sol1: right = mid - 1
sol2: right = mid

記法很簡單, 都長跟都短, sol1 code的長度永遠都會比sol2要多一些.
兩種方法記起來就可以處理99%的題目了.
```
[詳細解說](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0035.%E6%90%9C%E7%B4%A2%E6%8F%92%E5%85%A5%E4%BD%8D%E7%BD%AE.md)
