---
# System prepended metadata

title: LeetCode 35. Search Insert Position
tags: [Leetcode]

---


# LeetCode 35. Search Insert Position
[LeetCode 35. Search Insert Position](https://leetcode.com/problems/search-insert-position/description/) (<font color="#00AF9B"> Easy</font> 通過率: 47.7%)



## 限制條件
<ul>
<li>1 &lt;= nums.length &lt;= 10^4</li>
<li>-10^4 &lt;= nums[i] &lt;= 10^4</li>
<li>nums contains distinct values sorted in ascending order.</li>
<li>-10^4 &lt;= target &lt;= 10^4</li>
</ul>




### 解法 1
這題也是 binary search 的標準題目，只有最後的 insert 位置要注意而已，其他都沒有變。

- 時間複雜度: $O(lg(n))$
- 空間複雜度: $O(1)$

```cpp!=
class Solution {
public:
    int searchInsert(vector<int>&amp; nums, int target) {
        int min_index = 0, max_index = nums.size()-1;
        int mid_index = (max_index - min_index) + min_index;
        while(min_index &lt;= max_index)
        {
            mid_index = (max_index - min_index) + min_index;
            if(nums[mid_index] == target) return mid_index;
            else if(nums[mid_index] &lt; target) min_index = mid_index + 1;
            else if(nums[mid_index] &gt; target) max_index = mid_index - 1;
        }
        return max_index + 1;
    }
};

```
</int>