The purpose of this project is to show the implementation of Binary Search to find whether a given value is present in a sorted array using Python.
Binary Search is a searching algorithm applicable only when the array is sorted. It is a very efficient algorithm to run a search.
A binary search algorithm works on the idea of neglecting half of the array on every iteration. It keeps on splitting the array until it finds the value it is looking for in the given array. A binary search algorithm is much quicker than a simple linear search algorithm. The Time Complexity of binary search algoithm is O(log n).
The first thing to note is that a binary search algorithm always works on a sorted array. The element which is to be searched in the array is checked against the element at the middle index of the array.
If the given value is equal to the central index’s element, then the index is returned as an answer.
If the given value is lesser than the central index’s element, then the right subarray is discarded.
If the given value is greater than the central index’s element, then the left subarray is discarded.
The process is then repeated until the given value matches with the element at the central index of the array considered at that time or encounters the Limiting Case.
Limiting Case: The array considered at each time during the binary search has two boundaries, lower-bound and upper-bound. The Limiting case is encountered when the lower bound becomes greater than the upper bound. The process then stops immediately indicating that the desired value could not be found in the array.
Binary search can be performed in 2 ways, Recursive and Iterative. Here the Recursive implementation of binary search algorithm will be shown.
First we create a function binary_search:
def binary_search(arr, lb, ub, value):
Here arr is the array which is considered at each function call, lb is the lower-bound, ub is the upper-bound and value is the given element which is to be searched for in the array.
Next follows the code for the binary-search function:
# Limiting case, if lb(lower-bound) becomes higher than ub(upper-bound), return -1 if lb>ub: return -1 else: mid = (lb+ub) // 2 # Finding the middle index of the array # If value is at the middle index of the array if arr[mid]==value: return mid # If value is less than the element at the middle index, then it can only be present at the left subarray elif value < arr[mid]: return binary_search(arr, lb, mid-1, value) # Else the value can only be present at the right subarray else: return binary_search(arr, mid+1, ub, value)
The process continues until the desired value matches with the element at the middle index or the Limiting case is encountered:
If the desired value gets matched with the element at the middle index, the corresponding middle index is returned.
Or else, if the Limiting case gets encountered, "-1" is returned indicating that the value could not be found in the array
Finally, the index at which the value is present, or an error message, whichever is appropriate, is printed as the output accordingly.
# Test array arr = [ 3, 4, 9, 12, 16, 19, 25, 39, 54, 67, 71, 89, 101, 104, 113 ] # Taking the value input from user value = int(input("Enter a value to be searched for in the array: ")) # Function call result = binary_search(arr, 0, len(arr)-1, value) # Displaying the output if result == -1: print("Given value is not present in the array.") else: print("Given value is present at index " + str(result) + ".")
Above piece of code shows that a Test array has been considered and a value is taken as input from the user. The Test array, first index(0) as lower-bound, last index(size of array - 1) as upper-bound, value are passed consecutively to the binary_search function and the output is stored in result. The final output is shown to the user accordingly.