大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
廢話不多說開始今天的解題Day~

35. Search Insert Position

Question

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.

Example

Example1

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

Example2

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

Example3

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

Example4

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

Example5

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

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

解題

題目

首先先簡單的翻譯一下題目
給定一個有排序且數字不重複的陣列與一個目標值，要回傳這個目標值位於這個陣列的哪個位址。
如果這個目標值並不在陣列中，那則回傳目標值如果依照排序插入到陣列中，它所應該在的地方。

最後是時間複雜度的限制，最多只能是O(log n)

Think

由於時間複雜度的關係，如果直接用for loop跑全部陣列中的元素，時間複雜度會是O(n)，這樣就不符合題目的限制了!
所以這邊我們用Binary Search來解，Binary Search是一種對半切的概念，可以大幅減少需要找的可能性。

作法大致上是這樣

• 首先，會先有兩個指標low和upper存著最小跟最大的index，然後mid則是搜尋的數量同時也是切割點
  • 陣列長度如果是偶數，舉例來說，假設陣列長度為6，那mid的值會是(0 + 5)/2 = 2.5，這時取2或3都可以。
• 如果目標值大於我們剛剛得到的mid位址的值，那代表它在我們陣列對切後的右半邊，因為陣列是排序過的!我們只需要將low指標的index改成mid+1在繼續做Binary Search就好。
• 相反的，如果目標值是小於mid位址的值，就表示在右半邊，我們只需要將upper指標的index改成mid-1在繼續做Binary Search就好。
• 如果目標值有在陣列中，那上面Binary Search的演算法跑完，就會得到結果了。
• 接著，我們來處理不在陣列中的情況，由於Binary Search會一直逼近目標值，所以最後跳出迴圈前，我們可以得到最接近目標值的元素，如果目標值比它大，回傳mid+1；如果目標值小則是回傳mid!
• 而Binary Search的最差的時間複雜度是O(log n)，就是全部找完都沒找到或者是找到最後一步才發現目標值。
• 最後這題，用Python跟C的寫法差不多~

Code

Python

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        low = 0
        upper = len(nums)-1
        mid = 0
        
        # binarySearch
        while low <= upper:
            mid = int(round( ((low + upper) / 2), 0))
       
            if nums[mid] < target:
                low = mid + 1
            elif nums[mid] > target:
                upper = mid - 1
            else:
                return mid
        
        # If it doesn't contain in nums, we need to find where it would be inserted.
        if nums[mid] < target:
            return mid+1
        else:
            return mid

C

int searchInsert(int* nums, int numsSize, int target){
    int low = 0;
    int upper = numsSize - 1;
    int mid = 0;

    
    while (low <= upper){
        mid = (int)((upper+low)/2 + (upper+low)%2);
        
        if (nums[mid] < target){
            low = mid + 1;
        } else if (nums[mid] > target){
            upper = mid - 1;
        } else {
            return mid;
        }
        
    }
    return (nums[mid]<target? (mid+1) : mid);
}

Result

• Python

  • 

• C

  • 

大家明天見