Binary Search Algorithm With Python

Week A14: 03rd-09th Feb2025

This week when solving assignments I got lost on various problems, Here I am presenting with Binary search algorithm. The requirements for using this algorithm is data should be sorted. It is faster than linear search .Here is the code in python for BSA if the data is sorted in ascending order

def binary_search(my_list,target_value):
    Left, Right = 0, len(my_list) -1 
    while Left <= Right:
        Mid = Left + (Right-Left)//2 
        print(f'Left : {Left}, Mid : {Mid}, Right : {Right}')
        print(f'My_List: {my_list}, Current_value: {my_list[Mid]}, Target_Value: {target_value}')
        if my_list[Mid] == target_value:
            return Mid 
        elif my_list[Mid] < target_value:
            Left = Mid +1
        else:
            Right = Mid -1
    return -1 

The steps included are

Step-1

we initialize Left and Right variables to the extremes of the list as indexing starts from zero Left will be zero and Right will be len(my_list) -1

Setp-2

we don’t know how many loops it will take for finding the element so we can’t use iteration over a sequences like for loop so we need to use while loop until a certain conditions are met and the condition here is loop until either Left becomes greater than Right or Right becomes lesser than Left

Step-3

Find the middle value using Mid = Left + (Right-Left)//2 we can’t directly use (Left + Right)//2 because of overflow issue.

I.e. we know from basic math

Let x,y be +ve integers and x,y < M where m is max value allowed by the user (in computers if we use int8 data type M will be 2⁶³ -1)

Get write_avis’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

x + (y — x) <= y and we can say x + (y — x)/2<= y every value lies below M

however if we use (x+y)/2 <=y we don’t know what is x and y and whether x + y will be less than M in this case the addition of those variables can cause overflow

Step-4

This is the important step which controls the termination condition of the while loop

calculate the value of the element at the index Mid

if the value is equal to the target value then return the index position which terminates the while loop directly

if the value is greater than target value we can assign the Left variable to Mid +1 position and continue the loop

and if value is less than target value we can move the Right variable to Mid -1 position and continue the loop

The +1 and -1 here are very important because after looping continuously we can’t reach Left > Right or Right < Left in fact we can’t even reach Left = Right and the Mid value will be struck between either Left or Right and loops indefinitely. if the target value is either extreme value or don’t exist in the loop, achieving the loop termination condition will be impossible

Step -5

If the loop doesn’t return anything it means the element doesn’t exist in our list so we finally return -1 which means the value is out of list

Here is what happens if we don’t use Mid +1 and Mid -1 in the update statements

my_list = [1,2,3,4,5,6]
target_value = 6

# With Left = Mid +1 and Right = Mid -1 
binary_search(my_list,target_value)

>>> Output
Left : 0, Mid : 2, Right : 5
My_List: [1, 2, 3, 4, 5, 6], Current_value: 3, Target_Value: 6

Left : 3, Mid : 4, Right : 5
My_List: [1, 2, 3, 4, 5, 6], Current_value: 5, Target_Value: 6

Left : 5, Mid : 5, Right : 5
My_List: [1, 2, 3, 4, 5, 6], Current_value: 6, Target_Value: 6

... 5

## Without +1 and -1 i.e.,
# With Left = Mid and Right = Mid 
binary_search(my_list,target_value)

>>> Output 

Left : 0, Mid : 2, Right : 5
My_List: [1, 2, 3, 4, 5, 6], Current_value: 3, Target_Value: 6

Left : 2, Mid : 3, Right : 5
My_List: [1, 2, 3, 4, 5, 6], Current_value: 4, Target_Value: 6

Left : 3, Mid : 4, Right : 5
My_List: [1, 2, 3, 4, 5, 6], Current_value: 5, Target_Value: 6

Left : 4, Mid : 4, Right : 5
My_List: [1, 2, 3, 4, 5, 6], Current_value: 5, Target_Value: 6

Left : 4, Mid : 4, Right : 5
My_List: [1, 2, 3, 4, 5, 6], Current_value: 5, Target_Value: 6

Left : 4, Mid : 4, Right : 5
My_List: [1, 2, 3, 4, 5, 6], Current_value: 5, Target_Value: 6

Left : 4, Mid : 4, Right : 5
My_List: [1, 2, 3, 4, 5, 6], Current_value: 5, Target_Value: 6

.....