Binary search in python using recursion

Written by

Himani Kohli

In this program, we will be learning how to perform a binary search using recursion. A function is defined to perform binary search in the given array.

The main task is to search for a sorted array repeatedly by dividing the search interval by half.

If the search value is less than the middle item then narrow the interval to the lower half. Otherwise, narrow it to the upper half. Here, we need to continuously check for the result whether it is present or not.

Algorithm:

1. The term and first term is initialized 4 and 0 respectively.
2. Array b[] is defined and length of b[] is stored in a variable named last.
3. Define a function binary(a,fir,las,term).
4. Check if term is greater than middle term, then call the function binary(a, mid, las,term) recursively.
5. Else if the term is less than the middle term then call the function binary(a,fir, mid, term)
6. Else if the term is equal to the middle term print “number found” with index at mid+1
7. Else print “number is not there in the array”
8. Exit

Code:

``````def binary(a, fir, las, term):
mid=int((fir+las)/2)
if term>a[mid]:
binary(a, mid, las, term)
elif term<a[mid]:
binary(a,fir, mid, term)
elif term==a[mid]:
print("Number found at", mid+1)
else:
print("Number is not there in the array")
b=[1,2,3,4,5]
fir=0
las=len(b)
term=4
````binary(b,fir,las,term)````

Output:

``Number found at 4``