---
# System prepended metadata

title: 'LeetCode #35 [Search Insert Position](https://leetcode.com/problems/search-insert-position/)'
tags: [Binary Search, LeetCode, Medium]

---

###### tags: `LeetCode` `Medium` `Binary Search`
# LeetCode #35 [Search Insert Position](https://leetcode.com/problems/search-insert-position/)
### (Medium)

給定一個排序數組和一個目標值，在數組中找到目標值，並返回其索引。如果目標值不存在於數組中，返回它將會被按順序插入的位置。

請必須使用時間複雜度為 O(logn) 的算法。

---
需要透過Binary Search才能達到O(logn)的時間複雜度, 二元搜尋的重點:左閉右開, 也就是搜尋範圍為: 左<=搜尋範圍<右, 可避免許多邊界問題, 二元搜尋的範圍[可參考這篇](https://www.zhihu.com/question/36132386)。

---
```
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, h = nums.size();
        while(l<h){
            int mid = l + (h-l)/2;
            if(nums[mid]<target)l=mid+1;
            else h=mid;
        }
        return l;
    }
};
```
