Binary Search Program in Python

In this article, you will learn and get code to implement binary search in a Python program. Here are the list of programs on binary search:

• Binary Search using List with Ordered Inputs
• Binary Search with Random Inputs of Given Size
• Binary Search using for Loop

Before going through these programs, if you're not aware about the topic, then refer to binary search logic and algorithm to get every required thing.

Binary Search using List

This program searches a number entered by user using binary search technique. The program receives 10 numbers from user and then a number to search using binary search.

nums = []
print("Enter 10 Numbers (in ascending order):")
for i in range(10):
    nums.insert(i, int(input()))
print("Enter a Number to Search:")
search = int(input())
first = 0
last = 9
middle = (first+last)/2
middle = int(middle)
while first <= last:
    if nums[middle]<search:
        first = middle+1
    elif nums[middle]==search:
        print("The Number Found at Position:")
        print(middle+1)
        break
    else:
        last = middle-1
    middle = (first+last)/2
    middle = int(middle)
if first>last:
    print("The Number is not Found in the List")

Here is its sample run:

Now supply any 10 numbers say 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 and then a number say 60 to search. Here is the sample run with exactly these inputs:

The range() function returns a sequence of values. Its limit decided with its argument. For example:

for i in range(10):
    print(i)

prints the value of i ten time starting from 0 to 9. Therefore 0, 1, 2, 3 ,4, 5, 6, 7, 8, 9 gets printed on output. Each number printed in new line. Therefore the following code (from above program):

for i in range(10):

is used to execute the following statements:

nums.insert(i, int(input()))

ten number of times with value of i from 0 to 9.

Note - The insert() function is used to insert an element to the list (nums[] here). Therefore user is allowed to enter the value ten times. And all the values gets stored in nums[] in following way:

• First number entered by user gets stored in nums[i] or nums[0]
• Second number gets stored in nums[1]
• Third number gets stored in nums[2]
• and so on upto
• Tenth number gets stored in nums[9]

Note - In above program, the position is printed with middle+1 value, because indexing starts with 0. Therefore 0^th index's value is referred as first number.

Binary Search with Random User Inputs of Given Size

This program is similar to previous program with two extra features. The first one is, this program allows user to define the size of list. The second one is, this program doesn't cares about the order, user enters the data. Because, we've implemented the code to sort the list before applying the binary search technique to search a number

nums = []
print(end="How Many Number to Enter ? ")
tot = int(input())
print(end="Enter " + str(tot) + " Numbers: ")
for i in range(tot):
    nums.insert(i, int(input()))

for i in range(tot-1):
    for j in range(tot-i-1):
        if nums[j]>nums[j+1]:
            temp = nums[j]
            nums[j] = nums[j+1]
            nums[j+1] = temp

print(end="\nThe List is: ")
for i in range(tot):
    print(end=str(nums[i]) + " ")

print(end="\nEnter a Number to Search: ")
search = int(input())
first = 0
last = tot-1
middle = int((first+last)/2)
while first <= last:
    if nums[middle]<search:
        first = middle+1
    elif nums[middle]==search:
        print("\nThe Number Found at Position: " + str(middle+1))
        break
    else:
        last = middle-1
    middle = int((first+last)/2)
if first>last:
    print("\nThe Number is not Found in the List")

Here is its sample run with following user inputs:

• 6 as size of numbers
• 10, 60, 20, 50, 40, 30 as 6 numbers
• 30 as the number to search

Based on exactly these inputs, here is the sample run:

Note - Position of the entered number say 30 gets calculated based on sorted list, not on the original (unordered) list. Because binary search technique works on sorted list.

Binary Search using for Loop

To create the same program as of previous one, but using for loop. Then the main thing to change is:

while first <= last:

with this:

for first in range(last+1):

Here is the complete program for binary search using for loop in python:

nums = []
chk = 0
print(end="How Many Number to Enter ? ")
tot = int(input())
print(end="Enter " + str(tot) + " Numbers: ")
for i in range(tot):
    nums.insert(i, int(input()))

for i in range(tot-1):
    for j in range(tot-i-1):
        if nums[j]>nums[j+1]:
            temp = nums[j]
            nums[j] = nums[j+1]
            nums[j+1] = temp

print(end="\nThe List is: ")
for i in range(tot):
    print(end=str(nums[i]) + " ")

print(end="\nEnter a Number to Search: ")
search = int(input())
first = 0
last = tot-1
middle = int((first+last)/2)
for first in range(last+1):
    if nums[middle]<search:
        first = middle+1
    elif nums[middle]==search:
        print("\n" + str(search) + " Found at Position: " + str(middle+1))
        chk = 1
        break
    else:
        last = middle-1
    middle = int((first+last)/2)
if chk!=1:
    print("\n" + str(search) + " is Not Found in the List!")

Here is its sample run:

Python Online Test