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
Recommended:-Python Program to Swap Characters of Given String
Recommended:-Swap First Two Characters in Each String in Python
Recommended:-Python Split String into Array of Characters
Recommended:-Python Program to Reverse String Using Stack
Recommended:-Python Insert Element at Specified Index in List
Recommended:-Python Program to Swap Two Elements in a List
Recommended:-How to Take Input List From User in Python
Recommended:-Python Program to Find LCM of Two Numbers
Recommended:-Python Add and Remove Elements From List
Recommended:-Python Find Difference of Two Lists
Recommended:-Python Program to Split Even and Odd Numbers in List
Recommended:-Python Program Count vowels in String
Recommended:-Python Program to Find HCF or GCD of Two Numbers
Recommended:-Python Program to find Sum of N Natural Numbers
Recommended:-Python Program to Find the Square Root of Number
Recommended:-Python Program to Check Armstrong Number