Python Program for Binary Search

Python program for binary search; Through this tutorial, i am going to show you how to implement binary search program in python.

Binary Search is applied on the sorted array or list of large size. It’s time complexity of O(log n) makes it very fast as compared to other sorting algorithms. To use binary search on a collection, the collection must first be sorted.

Python Program for Binary Search

• Python Program for Binary Search
• Python program to implement binary search using recursion

Python Program for Binary Search

# Binary search function
def binarySearchAlgo(xlist, key):
    a = 0
    b = len(xlist)
    while a < b:
        c = (a + b)//2
        if xlist[c] > key:
            b = c
        elif xlist[c] < key:
            a = c + 1
        else:
            return c
    return -1
 
# input a list of elements
xlist = input('Enter the sorted list of numbers: ')
#split a element
xlist = xlist.split()
xlist = [int(x) for x in xlist]
# search for in list
key = int(input('The number to search for: '))
# call binary search function
index = binarySearchAlgo(xlist, key)
if index < 0:
    print('{} was not found.'.format(key))
else:
    print('{} was found at index {}.'.format(key, index))

After executing the program, the output will be:

Enter the sorted list of numbers:  1 2 3 4 5 6 7 8 9
The number to search for:  8
8 was found at index 7.

Python program to implement binary search using recursion

# Python code for recursive binary search
# Returns index of key in xlist if present, else -1 
def binarySearch (arr, l, r, x): 
	# Check base case 
	if r >= l: 
		mid = l + (r - l)//2
		# If element is present at the middle itself 
		if arr[mid] == x: 
			return mid 
		
		# If element is smaller than mid, find in left sub array
		elif arr[mid] > x: 
			return binarySearch(arr, l, mid-1, x) 
		# Otherwise find the element in right subarray 
		else: 
			return binarySearch(arr, mid+1, r, x) 
	else: 
		# Element is not present in the list 
		return -1
# input a list of elements
xlist = input('Enter the sorted list of numbers: ')
#split a element
xlist = xlist.split()
xlist = [int(x) for x in xlist]
# search for in list
key = int(input('The number to search for: '))
# Function call 
result = binarySearch(xlist, 0, len(xlist)-1, key) 
if result != -1: 
	  print('{} was found at index {}.'.format(key, result))
else: 
    print('{} was not found.'.format(key))

After executing the program, the output will be:

Enter the sorted list of numbers:  1 2 3 4 5 6 7 8
The number to search for:  6
6 was found at index 5.

Recommended Python Tutorials