大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
废话不多说开始今天的解题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

  • 

大家明天见