Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

describe

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 1:

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

Example 2:

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

Example 3:

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

Example 4:

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

Example 5:

Input: nums = [1], target = 0
Output: 0
Copy the code

Note:

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

parsing

If target is in nums, return the index of its location. If target is not in nums, return the index of its location. Returns an index that guarantees that target will remain in order after nums is inserted. The idea is simple:

  • If target is in nums, return nums.index(target)
  • Otherwise, each element in nums, num, is iterated, and if num is greater than target, the index of the current position is returned
  • If no appropriate index position is found, target is greater than all elements in numS

The time complexity of our algorithm is order (log n). Obviously, we can use dichotomy directly to satisfy the problem, but I just don’t use it

answer

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if target in nums:
            return nums.index(target)
        for i, num in enumerate(nums):
            if num > target:
                return i
        return len(nums)

        	      
		
Copy the code

The results

Given in the Python online submission for Search Insert Position. Memory Usage: Submissions in Python online submissions for Search Insert Position.Copy the code

parsing

I’m kidding. I would have used binary search. Have slightly ~

answer

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        l, r = 0, len(nums)-1
        while l <= r:
            mid = (l + r)//2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        return l
        
Copy the code

The results

Given the given list in the Python online submission. Memory Usage: 10000 ms 13 MB, less than 97.13% of Python online submissions for Search Insert Position.Copy the code

Original link: leetcode.com/problems/se…

Your support is my biggest motivation