codescracker
python

Binary Search Program in Python



« Python Examples Python Tutorial »


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:

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.

# ----codescracker.com----

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:

binary search in python

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:

binary search in python using list

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:

Note - In above program, the position is printed with middle+1 value, because indexing starts with 0. Therefore 0th index's value is refered 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 implented the code to sort the list before applying the binary search technique to search a number

# ----codescracker.com----

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:

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

binary search using while loop python

Note - Position of the entered number say 30 gets calcualted 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:

# ----codescracker.com----

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:

binary search using for loop python

« Python Examples Python Tutorial »