leetcode 35. Search Insert Position（python）

Little knowledge , Great challenge ！ This article is participating in “ A programmer must have a little knowledge ” Creative activities .

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 code 

Example 2:

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

Example 3:

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

Example 4:

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

Example 5:

Input: nums = [1], target = 0
Output: 0
 Copy 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 code 

analysis

According to the meaning , Gives an ordered list of integers nums And an integer target , If target stay nums in , Then directly return the index of the location , If target be not in nums in , An index guarantee is returned target Insert nums After that, it is still orderly . The idea is simple ：

• If target stay nums in , Go straight back to nums.index(target)
• Otherwise traverse nums Every element in num , If num Greater than target Directly return the index of the current location
• After traversal, if the appropriate index position is still not found , explain target Greater than nums All elements in , Go straight back to nums It's just as long as you want

The time complexity of our algorithm is required to be O(log n) , Obviously, the meaning of the question can be satisfied by directly using dichotomy , But I just don't have to , Ah, just play ～

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 code 

Running results

Runtime: 28 ms, faster than 96.37% of Python online submissions for Search Insert Position.
Memory Usage: 14.2 MB, less than 25.57% of Python online submissions for Search Insert Position.
 Copy code 

analysis

I lied to you , I'm sure I'll use the binary search method . 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 code 

Running results

Runtime: 38 ms, faster than 43.70% of Python online submissions for Search Insert Position.
Memory Usage: 14 MB, less than 97.13% of Python online submissions for Search Insert Position.
 Copy code 

Original link ：leetcode.com/problems/se…

Your support is my greatest motivation