Can you really write binary search - variant binary search

Preface

In fact, I have written an article about Variant binary search I've got my blog , But recently, I found that my previous understanding of variant binary search was not deep enough , And compared with the previous implementation of blog , This article has a different implementation , Although the details are different .

Two ways of thinking

Find the element in the loop body

def binarySerach(nums, key):
    left = 0
    right = len(nums) - 1
    
    while( left <= right ):
        mid = (left + right) >> 1   # Divide 2, But round down 
        if nums[mid] == key:  # If mid Element is key, Then find the answer 
            return mid
        elif nums[mid] < key:  # If mid The element is less than key, You need to move the search range to a large number . Next search [mid+1, right]
            left = mid + 1   # And the index of the target , Should be at least mid Big , therefore left As the mid+1
        elif nums[mid] > key: # Next search [left, mid-1]
            right = mid - 1
        
    return -1

• This kind of writing , There are three branches in the loop , Because there needs to be a branch to judge mid Whether the element is key, If so, go straight back .
• When there is only one element in the interval （ namely left and right identical ）, The loop body will also be executed once .

Narrow the search interval in the loop

This idea is mainly used for variant binary search , There are two types of questions ： Divide the array into <key and >=key Two parts 、 Divide the array into <=key and >key Two parts .

This kind of thinking is different from the previous one ：

1. When there is only one element in the interval （ namely left and right identical ）, The loop body will not be executed , Instead, exit the loop directly .
2. There are only two branches in the loop , Because this kind of thinking requires two pointers to reach the position , To exit the cycle . Determine the task that the pointer points to the element , The code outside the loop , natural , There are only two branches in the loop .

For example, array [0,1,2,3,4,5,6] and key = 3, If you use the first idea , First cycle I found it . But if you use the second idea , be Multiple cycles must be performed , Until both pointers stay at the index 3 after , And then exit the cycle , Then determine whether it is key. This is the biggest difference between the two ideas .

The specific details of this idea ：

• the reason being that while( left < right ), So when leaving the loop , It must be left be equal to right, Compared with the previous idea , This kind of thinking meets left be equal to right It's out of the loop .
• Because it is necessary to ensure that when leaving the cycle left be equal to right Of , So for left and right To deal with ： One of them must be directly equal to mid, The other is the standard plus or minus one .
• For the branch case in the loop body ： Need to put = Branches merge into one of the other two branches , To conform to the meaning of the topic .
• Because leaving the cycle is left be equal to right Of , And when the maximum index or the minimum index is encountered , The cycle will stop , But the maximum and minimum index that stays may not meet the requirements of the question . Therefore, special inspection is required .

Divide the array into <key and >=key Two parts

find first >=key The elements of , If not, return to -1

1. Two pointers stay at the minimum index （ namely 0 Indexes ）.
2. Two pointers stay , Except for the minimum index and the maximum index .
3. Two pointers stay at the maximum index .

Obviously , The above three situations , Only the last one needs special inspection , This situation may require a return -1, When the last element does not conform >=key when . The first two cases , Where the two pointers stay must be consistent >=key Of .

def binarySerach(nums, key):
    left = 0
    right = len(nums) - 1
    
    while( left < right ):
        mid = (left + right) >> 1 # Rounding down 
        
        if nums[mid] >= key:  
            right = mid 
        else:#nums[mid] < key
            left = mid+1
    if left == len(nums)-1 and nums[left] < key:
        return -1   
    return left

li = [1,2,4,5,7,7,7,7,7,7, 7,10,13]
ll = [0,1,2,3,4,5,6,7,8,9,10,11,12]  # This array is just for you to compare the index 

print(binarySerach(li,6))# Output 4
print(binarySerach(li,7))# Output 4
print(binarySerach(li,14))#left by 12, That is, the maximum index , Need to check 
print(binarySerach(li,-1))#left by 0, That is, the minimum index , There is no need to check 

#  because nums[mid] >= key It is the whole we want , Therefore, two cases greater than and equal to must be in one branch 
#  So the boundary in this branch moves , It must be directly equal to mid Of , Because to the last cycle this mid It must be 
#  The index we want .
#  And the other branch , Because it's definitely not what we want , So it must be mid Change in ( Add one or subtract one )
#  the reason being that mid The operation that produces the change is left = mid+1, So take mid It must be rounded down 

• Because to find the first >=key The elements of , therefore nums[mid] >= key In the branch , On the border （ Boundary refers to left or right） The treatment of must be directly equal to mid. such , The two pointers will eventually fall to the first >=key Elements of . By contrast , In another branch , The operation of the boundary must be plus or minus one .
• Because now it's left = mid+1 and right = mid, therefore mid It must be rounded down , Will not lead to the final dead cycle .
• because >=key The element of is on the right , So according to the above figure , It is necessary to specially check the case that the index is the maximum index .

find first key The elements of , If not, return to -1

def binarySerach(nums, key):
    left = 0
    right = len(nums) - 1
    
    while( left < right ):
        mid = (left + right) >> 1   
        
        if nums[mid] >= key:  
            right = mid 
        else:#nums[mid] < key
            left = mid+1
    if nums[left] == key:
        return left   
    return -1

li = [1,2,4,5,7,7,7,7,7,7, 7,10,13]
ll = [0,1,2,3,4,5,6,7,8,9,10,11,12]  # This array is just for you to compare the index 

print(binarySerach(li,6))# Output -1
print(binarySerach(li,7))# Output 4

There is no need for any special examination , Directly see whether it is key that will do .

Find the last one <key The elements of , If not, return to -1

def binarySerach(nums, key):
    left = 0
    right = len(nums) - 1
    
    while( left < right ):
        mid = (left + right+1) >> 1 # Rounding up 
        
        if nums[mid] >= key:  
            right = mid-1
        else:#nums[mid] < key
            left = mid
    if left == 0 and nums[left] >=key:
        return -1
    return left

li = [1,2,4,5,7,7,7,7,7,7, 7,10,13]
ll = [0,1,2,3,4,5,6,7,8,9,10,11,12]  # This array is just for you to compare the index 

print(binarySerach(li,6))# Output 3
print(binarySerach(li,7))# Output 3
print(binarySerach(li,1))# Output -1, Note that this is an invalid index 

• Because now I want to <key The elements of , therefore nums[mid] < key The branch is opposite to the boundary （ Boundary refers to left or right） The operation of must be directly equal to mid. By contrast , In another branch , The operation of the boundary must be plus or minus one .
• Because now it's left = mid and right = mid-1, therefore mid It must be rounded up , Will not lead to the final dead cycle .
• because <key The element of is on the left , So according to the above figure , The index requiring special inspection is 0 The situation of .

Divide the array into <=key and >key Two parts

This chapter is all about mirroring , The analysis is completely similar , I won't go into that .

Find the last one <=key The elements of , If not, return to -1

def binarySerach(nums, key):
    left = 0
    right = len(nums) - 1
    
    while( left < right ):
        mid = (left + right+1) >> 1   
        
        if nums[mid] <= key:  
            left = mid
        else:#nums[mid] > key
            right = mid-1
    if left == 0 and nums[left] >=key:
        return -1
    return left

li = [1,2,4,5,7,7,7,7,7,7, 7,10,13]
ll = [0,1,2,3,4,5,6,7,8,9,10,11,12]  # This array is just for you to compare the index 

print(binarySerach(li,8))# Output 10
print(binarySerach(li,7))# Output 10
print(binarySerach(li,0))# Output -1, Note that this is an invalid index 

Find the last one key Elements , If not, return to -1

def binarySerach(nums, key):
    left = 0
    right = len(nums) - 1
    
    while( left < right ):
        mid = (left + right+1) >> 1   
        
        if nums[mid] <= key:  
            left = mid
        else:#nums[mid] > key
            right = mid-1
    if nums[left] == key:
        return left   
    return -1

li = [1,2,4,5,7,7,7,7,7,7, 7,10,13]
ll = [0,1,2,3,4,5,6,7,8,9,10,11,12]  # This array is just for you to compare the index 

print(binarySerach(li,8))# Output -1
print(binarySerach(li,7))# Output 10
print(binarySerach(li,0))# Output -1

find first >key The elements of , If not, return to -1

def binarySerach(nums, key):
    left = 0
    right = len(nums) - 1
    
    while( left < right ):
        mid = (left + right) >> 1   
        
        if nums[mid] <= key:  
            left = mid+1
        else:#nums[mid] > key
            right = mid

    if left == len(nums)-1 and nums[left] <= key:
        return -1   
    return left


li = [1,2,4,5,7,7,7,7,7,7, 7,10,13]
ll = [0,1,2,3,4,5,6,7,8,9,10,11,12]  # This array is just for you to compare the index 

print(binarySerach(li,8))# Output 11
print(binarySerach(li,7))# Output 11
print(binarySerach(li,13))# Output -1

Compared with the previous blog implementation

If you read the previous article Binary search blog , You'll find that , The difference from this implementation is ：

• In the previous blog , When exiting the loop ,right On the left ,left On the right , And the two must be adjacent . And one of the pointers must fall on the qualified boundary .
  • The pointer may be the minimum index minus one , It may also be the maximum index plus one .
• In this paper , When exiting the loop ,left and right equal .
  • The pointer can only be between the minimum index and the maximum index .（ That is, it must be a legal index ）