Question 35 of the Likou Question Bank - Search for insertion position

Question description

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 sequentially.

 Please use an algorithm with a time complexity of O(log n).

 Example 1:

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

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

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

 hint:

 1 <= <= 104
 -104 <= nums[i] <= 104
 nums is an ascending order of no repeat elements.
 -104 <= target <= 104

Analysis

The question requires us to use the time complexity of O(log₂n) algorithm, then we cannot simply and roughly traverse it. According to the order of the question, the array of the question is ordered, and we can easily think of using dichotomy to find data. If we find the element whose middle offset is equal to target, then we can directly return the middle. If the element is not found, just return the value of left directly when exiting the loop. Because it is very simple, I won’t go into too much details here!

Look directly at the code:

class Solution:
     def searchInsert(self, nums: List[int], target: int) -> int:
         # Obviously, binary search is required
         left= 0
         right= len(nums) -1
         while left <= right:
             middle = (left + right) // 2 # Intermediate index
             if nums[middle] == target:
                 Return middle
             if nums[middle] > target:
                 right = middle - 1
             if nums[middle] < target:
                 left = middle + 1
         if left > right:
             return left

Summarize

A little knowledge point: If the array is ordered, then you can use the binary search method when searching, and the time complexity is O(log₂n)!