Python Program for Binary Search

Python Program for Binary Search

Python Program for Binary Search; Through this tutorial, we would love to show you how to implement a program to binary search 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 with Function
  • Python program for binary search using recursion function

Algorithm of Binary Search

Implement binary search following the below steps:

  1. Start with the middle element of the given list:
    • If the target value is equal to the middle element of the array, then return the index of the middle element.
    • Otherwise, compare the middle element with the target value,
      • If the target value is greater than the number in the middle index, then pick the elements to the right of the middle index, and start with Step 1.
      • If the target value is less than the number in the middle index, then pick the elements to the left of the middle index, and start with Step 1.
  2. If a match is found, return the index of the element matched.
  3. Otherwise, return -1

Python Program for Binary Search with Function

# 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 for binary search using recursion function

# 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 Programs

  1. Python Program to Find/Calculate Average of 3, 4, 5…n numbers
  2. Python Program to Print ASCII Value of Character
  3. Write a Program to Calculate Simple Interest in Python
  4. Python Program to Compute Compound Interest
  5. Leap Year Program in Python
  6. Python Program to Print Star Pattern
  7. Number Pattern Programs in Python
  8. Python Program to Print Even and Odd numbers From 1 to N
  9. Python Abs() Function: For Absolute Value
  10. How to Check Whether a Number is Fibonacci or Not in Python
  11. Python: Program to Find Power of Number
  12. Python Program to Find Largest/Maximum of n Numbers
  13. Python Program to Find The Net Bill Amount After Discount
  14. Python Program to Print Numbers From N to 1 and 1 to N
  15. Python Program to Print Numbers Divisible by 3, 5, 7
  16. Python Program to Print Prime Number 1 to N
  17. How to Find Square of Number in Python
  18. Python Program to Calculate Cube of Number
  19. Python Random Number Generator Code
  20. Python Program to Calculate n-th term of a Fibonacci Series
  21. Zip Zap Zoom Python Program
  22. Python: program to convert Celsius to Fahrenheit
  23. Python Program to Swap Two Numbers
  24. Python Program to Get Standard Deviation
  25. Python Program to Find the Variance
  26. Python Program to Convert Height in cm to Feet and Inches
  27. Python Program to Convert Meters into Yards, Yards into Meters
  28. Python Program to Convert Kilometers to Meters, Miles
  29. Python Program to Find Perfect Number
  30. Python: Program to Find Strong Number
  31. Python Program Create Basic Calculator
  32. Python Program For math.floor() Method
  33. Python Program to Find Sum of Series 1/1! 2/2! 3/3! …1/n!
  34. Python: Program to Convert Decimal to Binary, Octal and Hexadecimal
  35. Python Program to Find Roots of Quadratic Equation
  36. Python Program to Print Alphabets from A to Z in Uppercase and Lowercase
  37. Python Program to Check Given Input is Alphabet, Number or Special Character
  38. Python Program to Check IF a Number is Power of Another Number
  39. Python Check Binary Representation of Given Number is Palindrome or Not
  40. Python Program to Calculate the Area of a Rectangle
  41. Python Program to Calculate Area of Triangle
  42. Python Program to Print Binary Value of Numbers From 1 to N
  43. Python Program to Find Sum Of Even and Odd numbers From 1 to N
  44. Python Program to Calculate Simple and Compound Interest
  45. Python Program to Find Factors of a Number

AuthorAdmin

My name is Devendra Dode. I am a full-stack developer, entrepreneur, and owner of Tutsmake.com. I like writing tutorials and tips that can help other developers. I share tutorials of PHP, Python, Javascript, JQuery, Laravel, Livewire, Codeigniter, Node JS, Express JS, Vue JS, Angular JS, React Js, MySQL, MongoDB, REST APIs, Windows, Xampp, Linux, Ubuntu, Amazon AWS, Composer, SEO, WordPress, SSL and Bootstrap from a starting stage. As well as demo example.

Leave a Reply

Your email address will not be published. Required fields are marked *