LeetCode - 35. Search Insert Position

Easy

題目

Given a sorted array of distinct integers nums and a target value target, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) 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

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums contains distinct values sorted in ascending order.
-10^4 <= target <= 10^4

解題思路

這題是經典 Binary Search，重點不是找「有沒有」，而是找「應該插在哪裡」

如果我要找「某個值是否存在」
- 常用左閉右閉：
  - [left, right]
  - while(left <= right)
  - 更新就應該配套用：
    - right = mid - 1
    - left = mid + 1
如果我要找「第一個滿足條件的位置」
- 常用左閉右開：
  - [left, right)
  - while(left < right)
  - 更新就應該配套用：
    - right = mid
    - left = mid + 1
這題屬於第二種情況：
- 找「第一個 >= target 的位置」
- 即使 target 不存在，也能得到正確插入位置
因此使用 [left, right) 寫法：
- right = nums.size()
- 最後回傳 left

Solution Code

Time Complexity
O(log n)

Space Complexity
O(1)

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