Binary Search in Python Programming

Searching in Python

What is Binary Search in Python?

A Binary Search is a searching technique used in python to search an element from sequences like arrays and lists. Binary search only works on sorted lists or arrays.

Suppose we have a sorted list in ascending order, and we are looking for an element in the list, which is situated, at the end of the list. In this case, linear search is not suitable because it will scan each element from the start until it reached the last element that we are searching for in the list. In this situation, Binary Search is a more suitable and efficient searching technique compare to Linear Search.

In this searching technique, we compare the search element with the middle element of the list. If the search element is greater than the middle element, then we start searching in the right portion of the list after the middle element. If the search element is less then the middle element, then we start searching in the left portion of the list below the middle element. Now we will take only that portion in which the search element may be present and again compare the search element with the middle element of that portion. This process will be in iteration until we find the element, or there is no left or right portion left to search the element.

To clearly understand the binary search technique, let's go through its algorithm step by step with an example.

Binary Search Visualization

Suppose we have seven numbers stored in ascending order in a list as shown below. We want to search the number 17 in the list.

n is a variable that contains the number 17 we want to search in the list.

S is a variable stands for start index and contains the index 0.

E is a variable stands for end index and contains the index 6.

M is a variable stands for middle index and contains the index (S+E)/2=3.

The value of n=17 is not matching with the middle index value 12. The value of n is greater then the middle index value. So we will search in the right portion of the list starting after the middle index.

Now the value of S will be M+1=4.

The value of E remains the same, that is 6.

The value of M will be (S+E)/2=5.

The value of n=17 is not matching with the middle index value 37. The value of n is smaller then the middle index value. So we will search in the left portion of the list below the middle index.

The value of S remains same, that is 4.

Now the value of E will be M-1=4.

The value of M will be (S+E)/2=4.

Now the value of n=17 is matching with the middle index value 17. So, the search is successful and the element is found at index 4.

Algorithm for Binary Search

An algorithm is the steps used to implement the binary search in a python program.

Assume we have N numbers in ascending order, stored in a list. To implement the binary search on N numbers, the steps are as follows.

• Define a list to store N numbers in ascending order for binary search. Suppose we have defined a list with the name num.
• Store the number we want to search in a variable say x.
• Declare a variable f and set its value 0. For example f=0.
• Set the value of the start index variable S=0 and end index variable E=N-1.
• Run a while loop i till S<=E.
• Find the middle index M by dividing the sum of S and E by 2 and consider only the integer part of the result.
• Check if value of x is equal to the value of num[M] then print message Number found at index along with the value of M and set f=1 and then break the loop.
• Check If value of x is greater than the value at num[M] then set the start index S=M+1.
• If value of x is smaller than the value at num[M] then set the end index E=M-1.
• Outside the body of the loop i check if value of f is 0 then print the message Number not found.

Python Program for Binary Search

A Python program to search a number in a list having numbers in ascending order using binary search technique.

# define a list that contain numbers in ascending order
num=[2,5,9,12,17,37,86]

print('List: ',end='')
for n in num:
    print(n,end=' ')
print('\n')

# store the number in variable x to search in the list
x=int(input('Enter number to search '))

# set the value of variable f=0
f=0

# set the start index S, end index E with the start and end index of the list
S=0
E=len(num)-1

# run a while loop till S is less than or equal to E
while S<=E:

    # find the middle index M by dividing the sum of S and E by 2
    # and consider only the integer part of the result.
    M=(S+E)//2

    # check if value of x is equal to the value of num[M] then print message
    # 'Number found at index' along with the value of M and set f=1 and then break the loop
    if x==num[M]:
        print('Number found at index',M)
        f=1
        break

    elif x>num[M]:  # check if value of x is greater than the value at num[M] then set the start index S=M+1
        S=M+1

    elif x<num[M]:  # check if value of x is smaller than the value at num[M] then set the end index E=M-1
        E=M-1


# check if value of f is 0 then print number not found
if f==0:
    print('Number not found')

List: 2 5 9 12 17 37 86

Enter number to search 17
Number found at index 4

A Python program to search a number in a list having numbers in descending order using binary search technique.

# define a list that contain numbers in descending order
num=[86,37,17,12,9,5,2]

print('List: ',end='')
for n in num:
    print(n,end=' ')
print('\n')

# store the number in variable x to search in the list
x=int(input('Enter number to search '))

# set the value of variable f=0
f=0

# set the start index S, end index E with the start and end index of the list
S=0
E=len(num)-1

# run a while loop till S is less than or equal to E
while S<=E:

    # find the middle index M by dividing the sum of S and E by 2
    # and consider only the integer part of the result.
    M=(S+E)//2

    # check if value of x is equal to the value of num[M] then print message
    # 'Number found at index' along with the value of M and set f=1 and then break the loop
    if x==num[M]:
        print('Number found at index',M)
        f=1
        break

    elif x>num[M]:  # check if value of x is greater than the value at num[M] then set the end index E=M-1
        E=M-1

    elif x<num[M]:  # check if value of x is smaller than the value at num[M] then set the start index S=M+1
        S=M+1


# check if value of f is 0 then print number not found
if f==0:
    print('Number not found')

List: 86 37 17 12 9 5 2

Enter number to search 17
Number found at index 2

Binary Search Program Explanation

The explanation of the above program is given below in details.

List: 2 5 9 12 17 37 86

x = 17  Number to be search in the list
f = 0

S = 0   Start index
E = 6   End index

Running a while loop i till S<=E

When S = 0 and E = 6
  M = (S+E)/2 = 3
  Value of x=17 and num[3]=12
  Check if 17==12   17 is greater than 12
  So Start index will be S=M+1 = 4
  Now we will search 17 between index 4 and 6

When S = 4 and E = 6
  M = (S+E)/2 = 5
  Value of x=17 and num[5]=37
  Check if 17==37   17 is smaller than 37
  So End index will be E=M-1 = 4
  Now we will search 17 between index 4 and 4

When S = 4 and E = 4
  M = (S+E)/2 = 4
  Value of x=17 and num[4]=17
  Check if 17==17  Yes
  Number found at index 4

  f = 1
  Break the loop

Loop i ends

Check if f==0   No