In this tutorial, we will be understanding how to implement Binary Search with the help of Recursion. I hope by now you are familiar with both Binary Search and Recursion.
To make it simpler for you we will be covering them in brief.
What is Binary Search?
Binary search is an efficient and fast algorithm for finding an element in a sorted list of elements.
It finds elements by repeatedly dividing the array in half and then compare the middle of the division to identify in which division the element could be present.
In order to implement Binary Search, we need three-pointers namely lower bound, upper bound, and a middle pointer.
The division of a subarray is defined by lower bound and upper bound whereas the mid pointer value is compared to the value of the element that needs to be located.
Read More on Binary Search here: Binary Search Algorithm in Python
What is Recursion?
Now, Binary Search can be implemented in many ways, some of them are mentioned below:
In this tutorial, we will be implementing Binary Search with the help of recursion.
When one function calls itself can be a direct or indirect call in order to solve a smaller problem of the same type of a bigger problem, the technique is known as Recursion.
Read More on Recursion here: Recursion in Python
Binary Search Implementation using Recursion
Let’s implement the binary search algorithm using recursion in Python here. I’ve added the code with comments to help you understand what each line does.
def Binary_Search(arr,n,lb,ub,X):
# 1. List is empty
if(n==0):
print("ERROR!")
# 2. If element is not found lb exceeds ub
elif(lb>ub):
print("Not found!")
# 3. Keep searching for the element in array
else:
mid = int((lb+ub)/2)
if(arr[mid]==X):
print(mid+1)
elif(arr[mid]>X):
Binary_Search(arr,n,lb,mid,X);
elif(arr[mid]<X):
Binary_Search(arr,n,mid+1,ub,X);
arr = [1,2,3,4,5,6,7,8,9]
n = len(arr)
X = int(input())
Binary_Search(arr,n,0,n-1,X)
Outputs
Original List is: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Element to Search for: 90
Result: Not found!
Original List is: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Element to Search for: 5
Result: 5
Conclusion
In this tutorial, we understood how to implement Binary Search with the help of Recursion along with some basics of Binary Search and Recursion.
Hope you liked the tutorial! Thank you for reading!
Stay tuned for more such tutorials! 😇