# 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⁴</code>
- <code>-10⁴ <= nums[i] <= 10⁴</code>
- <code>nums</code> contains **distinct** values sorted in **ascending** order.
- <code>-10⁴ <= target <= 10⁴</code>

## Solution 1 - Binary Search
#### 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++

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

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:

兩種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)