1 subject

Given a sort 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 to where it will be inserted in sequence .
Please use a time complexity of O(log n) The algorithm of .

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

2 analysis

Insert with binary search , Pay attention to boundary judgment , Insertion position , If you insert target Than a Big , Then insert in a Behind . At this time, take an example to draw , You can understand .
such as nums = [1,3,5,6], target=4 and target=2

3 Python Realization

def searchInsert(self, nums: List[int], target: int) -> int:
    l, r = 0, len(nums)-1
    result = len(nums)
    while l <= r:
        mid = int((l+r)/2)
        if target<=nums[mid]:
            r = mid-1
            result = mid
        else:
            l = mid+1              
    return result