Binary search lower bound in Python

In this tutorial, we will learn about the Binary Search Lower Bound in Python. So before that let’s know what is Binary Search.

So, for example, you have a sorted list or a sorted array of n numbers and you want to find a particular number from that list, in that case, you first divide the list into two halves and if the value is less than the middle number, then narrow the interval into lower half, otherwise narrow it to the upper half.

Do these steps repeatedly until the middle value equals the searched value or if the searched value is not present in that list then the interval should be empty or return -1 as a result.

Binary search Lower Bound and Upper Bound

Now assume, the number you want to search from a particular list is present in that list more than one time. So in that case, either we want to know the lowest position of that number or the highest position of that number. Hence this lowest position of that number is called lower bound and the highest position is called an upper bound. You can refer to this below image for better understanding:

Binary search Lower Bound and Upper Bound

So now let’s start with our program,

Suppose I’m giving a list of sorted integers

nums = [1, 1, 2, 2, 2, 3, 5, 5, 6, 6, 6, 7, 8]

 

and you can clearly see that there are several numbers that are repeated more than once, so now assume I want to search the position of the number 2. Before searching the number we need to set the starting point and ending point of the list. The starting point is obviously 0 but the ending point should be the length of the list – 1. So we need to find out the length of the array as well.

 

tl = len(nums)   #Total Length of the List
sn = 2   #The number which you want to search

 

So we initialized the searched number and the length of the list. Now we need to make a function that will find the first occurrence of the searched number from the list. The function will have three arguments, such as the list, length of the list, and the value which will search.

 

def firstOccurance(numbers, length, searchnum):

 

Now inside the function, we need to initialize a variable answer which will have -1 as a default value. In case the searched number is not present in the list it will print -1, and also initialize the starting and ending point as well.

 

answer = -1  #If the number is not in the list it will return -1
start = 0    #Starting point of the list
end = length - 1     #Ending point of the list

Now we will make use of a while loop which will run until it found the lowest position of the searched number, in case the number is not present in the list, it will break when the ending point is equal to the starting point.

 

while start <= end:

Inside the while loop, we will initialize the middle point which is nothing but the average of starting and ending point.

 

middle = (start + end)//2    #Finding the middle point of the list

 

And now we will use the if-else statement, so the first condition for if statement is if the middle_value = searched number, then the answer is equal to the middle_value and endpoint is now middle-1. After that, for elif statement the condition will be if the middle_value > searched number then endpoint will be middle – 1 and the upper half will be ignored. And else the starting point will be middle + 1 and the lower part will be ignored.

 

if numbers[middle] == searchnum:
    answer = middle
    end = middle - 1
elif numbers[middle] > searchnum:
    end = middle - 1    
else:
    start = middle + 1

 

Now just return the answer. And it will print the position of the searched value. If the value is not present in the list it will print -1. So now if we summarize the function it becomes:

 

def firstOccurance(numbers, length, searchnum):
    answer = -1  #If the number is not in the list it will return -1
    start = 0    #Starting point of the list
    end = length - 1     #Ending point of the list
    
    while start <= end:
        middle = (start + end)//2    #Finding the middle point of the list
        
        if numbers[middle] == searchnum:
            answer = middle
            end = middle - 1
        elif numbers[middle] > searchnum:
            end = middle - 1    
        else:
            start = middle + 1
    
    return answer

 

And the overall program now becomes:

 

def firstOccurance(numbers, length, searchnum):
    answer = -1  #If the number is not in the list it will return -1
    start = 0    #Starting point of the list
    end = length - 1     #Ending point of the list
    
    while start <= end:
        middle = (start + end)//2    #Finding the middle point of the list
        
        if numbers[middle] == searchnum:
            answer = middle
            end = middle - 1
        elif numbers[middle] > searchnum:
            end = middle - 1    
        else:
            start = middle + 1
    
    return answer


nums = [1, 1, 2, 2, 2, 3, 5, 5, 6, 6, 6, 7, 8]
tl = len(nums)   #Total Length of the List
sn = 2   #The number which you want to search

ans = firstOccurance(nums, tl, sn)
print(ans)

 

The output of the above program is:

2

Now if change the value of the searched number, for example, sn = 9

 

nums = [1, 1, 2, 2, 2, 3, 5, 5, 6, 6, 6, 7, 8]
tl = len(nums)   #Total Length of the List
sn = 9   #The number which you want to search

ans = firstOccurance(nums, tl, sn)
print(ans)

 

It will print

-1

So now I hope you understand how to perform the binary search lower bound in python.

Leave a Reply

Your email address will not be published. Required fields are marked *