Binary search common questions

1. Find the first one greater than K The elements of

nums = [5,7,7,8,8,9,10,10]
target =8

left,right = 0,len(nums)-1
while(left<=right):
    mid = left+(right-left)//2   
    if nums[mid]<=target:
        left = mid+1
    elif nums[mid]>target:
        right = mid-1
left

 2. Find the last one ≤k The elements of

nums = [5,7,7,8,8,9,10,10]
target =8

left,right = 0,len(nums)-1
while(left<=right):
    mid = left+(right-left)//2   
    if nums[mid]<=target:
        left = mid+1
    elif nums[mid]>target:
        right = mid-1
right

 3. Find the first ≥k The elements of

nums = [5,7,7,8,8,9,10,10]
target =8

left,right = 0,len(nums)-1
while(left<=right):
    mid = left+(right-left)//2   
    if nums[mid]<target:
        left = mid+1
    elif nums[mid]>=target:
        right = mid-1
left

4. Find the last less than k The elements of

nums = [5,7,7,8,8,9,10,10]
target =8

left,right = 0,len(nums)-1
while(left<=right):
    mid = left+(right-left)//2   
    if nums[mid]<target:
        left = mid+1
    elif nums[mid]>=target:
        right = mid-1
right

One 、 Find... In an ordered array Numbers K Number of occurrences

The first solution ：

1. Find the last one Less than k Coordinates of the number of l ;

2. Find the first Greater than k Coordinates of the number of r ;

3. be Numbers k The number of ：r-l-1

The second solution ：

1. find The first one is greater than k The elements of r

2. Find the first one greater than k-1 The elements of l

3. be k The number of r-l

class Solution:
    def search(self, nums: List[int], target: int) -> int:

        def searchleft(target):
            left,right = 0,len(nums)-1
            while(left<=right):
                mid = left+(right-left)//2   
                if nums[mid]<=target:
                    left = mid+1
                elif nums[mid]>target:
                    right = mid-1
            return right    

        l = searchleft(target-1)
        r = searchleft(target)
        return r-l