題目：

給定一個排序的整數陣列 nums 和一個目標值 target：

• 如果 target 存在於陣列中，回傳其索引。
• 如果 target 不存在，則回傳它按順序應該插入的位置。

範例：
範例 1：

輸入：nums = [1,3,5,6], target = 5  
輸出：2

範例 2：

輸入：nums = [1,3,5,6], target = 2  
輸出：1

範例 3：

輸入：nums = [1,3,5,6], target = 7  
輸出：4

範例 4：

輸入：nums = [1,3,5,6], target = 0  
輸出：0

解題思路

因為題目有要求用 O(log n) 的演演算法完成，所以這題就是應用二元搜尋的方式來解題，while 迴圈的部份再注意一下結束條件，

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

時間複雜度：O(log n)
空間複雜度：O(1)

參考：
#35. Search Insert Position