35. （Search Insert Position）搜索插入位置

題目：

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

給定一個排序陣列和一個目標值，在陣列中找到目標值，并回傳其索引，如果目標值不存在于陣列中，回傳它將會被按順序插入的位置，

請必須使用時間復雜度為 O(log n) 的演算法，

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

示例 1:

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

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

示例 2:

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

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

示例 3:

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

Example 4:

Input: nums = [1,3,5,6], target = 0
Output: 0

示例 4:

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

Example 5:

Input: nums = [1], target = 0
Output: 0

示例 5:

輸入: nums = [1], target = 0
輸出: 0

Constraints:

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

提示:

• 1 <= nums.length <= 10 4 ^4 4
• -10 4 ^4 4<= nums[i] <= 10 4 ^4 4
• nums 為無重復元素的升序排列陣列
• -10 4 ^4 4 <= target <= 10 4 ^4 4

解題思路

方法：二分查找

當題目中只要求我們找到一個排序陣列中的一個目標值并回傳其索引值時，我們第一想到的就是二分查找，然而題目中還有一個條件當這個目標值不在時，回傳按順序插入的索引值，

我們使用position來定義插入的位置時:
滿足條件nums[positon-1] < < < target ≤ \leq ≤ nums[position]（即在一個有序陣列中找第一個大于target值的索引值，回傳按順序插入的索引值，

Python代碼

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1
        while(left <= right):
            mid = left + (right - left) // 2
            if (nums[mid] < target):
                left = mid + 1
            elif (nums[mid] > target):
                right = mid - 1
            else :
                return mid
        return left

Java代碼

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

C++代碼

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

    }
};

復雜度分析

時間復雜度：O( l o g n log_n logn?)，其中 n為陣列的長度，二分查找所需的時間復雜度為 O( l o g n log_n logn?)，

空間復雜度：O(1)，我們只存放若干變數，