• Difficulty:simple
  • The problem involves the algorithm:Binary search
  • Ideas:Binary search violence The target value is inserted into the array
  • Similar questions:

The title35. Search for insertion locations

Given a sorted array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, return the position where it will be inserted in order.

You can assume that there are no duplicate elements in the array.

Example 1:

Input:,3,5,6 [1], 5 output: 2 example 2: input:,3,5,6 [1], 2 output: 1 example 3: input:,3,5,6 [1], 7 output: 4 example 4: input:,3,5,6 [1], 0 output: 0Copy the code

Method one and two search

  • Complexity analysis:
    • Time complexity O(logN)))O(logN)))O(logN)) O(logN))), where NNN is the length of the array, each time reducing the size of the problem by half, so the time complexity is logarithmic
    • Space complexity O(1)O(1)O(1)

python

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

Method two: violent traversal

  • Complexity analysis:
    • Time complexity O(logN)) O(logN)))O(logN)) O(logN))), where NNN is the length of the array, the worst case traversal target value > the last value of the array
    • Space complexity O(1)O(1)O(1)

python

class Solution:
    def searchInsert(self, nums: List[int], target: int) - >int:
        if not nums:
            return 0
        if nums[-1] < target:
            return len(nums)
        for i in range(len(nums)):
            if nums[i] >= target:
                return i
Copy the code

java

class Solution {
    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        int ans = 0;
        if (len == 0) {return 0;
        }
        if (nums[len-1] < target) {
            return len;
        }

        for (int i = 0; i<len; i++) {if (nums[i] >= target) {
                ans = i;
                break; }}returnans; }}Copy the code

Method 3: After the target value is inserted into the array, it looks up the position (provides a new idea)

  • Their thinking:
    • The target value is inserted into the array
    • Query the position of the target value after sorting
  • Complexity analysis:
    • Time complexity O(logN)) O(logN)))O(logN)) O(logN))), where NNN is the length of the array, the worst case traversal target value > the last value of the array
    • Space complexity O(1)O(1)O(1)

python

class Solution:
    def searchInsert(self, nums: List[int], target: int) - >int:
        # Append regardless of whether the number is inside or not
        nums.append(target)
        # and then sort
        nums.sort()
        # return the index of the search
        return nums.index(target)

Copy the code