Several variants of binary search

Notice it’s all closed interval search

1. The basic

left = 0
right = len(nums)-1     #[left, right] closed interval
while left <= right:
    mid = left + (right - left) // 2
    if nums[mid] == target: 
        return mid
    elif nums[mid] < target: 
        left = mid + 1   
    elif nums[mid] > target:
        right = mid - 1     
return -1    Return -1 if left>right is not found
Copy the code

2. Look for the left edge

left = 0
right = len(nums)-1
while left <= right:
    mid = left + (right - left) // 2
    if nums[mid] == target: 
        right = mid - 1
    elif nums[mid] < target: 
        left = mid + 1   
    elif nums[mid] > target:
        right = mid - 1   
if left>=len(nums) ornums[left]! =target:return -1        # cross-border
return left
Copy the code

3. Look for the right boundary

left = 0
right = len(nums)-1
while left <= right:
    mid = left + (right - left) // 2
    if nums[mid] == target: 
        left = mid + 1
    elif nums[mid] < target: 
        left = mid + 1   
    elif nums[mid] > target:
        right = mid - 1   
if right<0 ornums[right]! =target:return -1        # cross-border
return right
Copy the code