Recursive Binary Search Function in Python

The binary search method is based on divide and conquer rules. It is basically applied on the sorted list of array of numbers. The binary search method performs in this way.

• Compare the number with middle number in the array
• if the number is equal to our data – it return the position of that data else
• if the number is smaller than the data then the staring index of list will start from one location higher than middle else
• if the number is larger than the data then the ending index of list will start one less positon of middle.

An iterative method for implementing Binary search method is as follows

x =[1,2,3,5,7,8,9,10,12,14,15,18,20,22]
data = 10
found =0
first=0
last =13
while (first<=last and found ==0):
    mid = int((first+last)/2)
    if(x[mid]==data):
       found =1
    if(x[mid]data):
        last = mid-1
if(found ==0):
    print("Data not found")
else:
    print("Data found")

Binary Search using Recursion

def binarySearch (arr, l, r, x): 
      if r >= l: 
        mid = (l + (r - l))//2
        if arr[mid] == x: 
            return mid 
        elif arr[mid] > x: 
            return binarySearch(arr, l, mid-1, x) 
        else: 
            return binarySearch(arr, mid+1, r, x) 
    else: 
        return -1

li = [1,2,3,4,5,6,7,8,9,10]
result = binarySearch(li,9,len(li),6)
if(result!=-1):
  print('Data found at index :',result)
else:
  print(' Data not found')

The output of the above program is as follows

rakesh@folio MINGW64 /e/python (master)
$ python -u "e:\python\functions\recursion\recursive_binary_search.py"
Data found at index : 5

Hope you have enjoyed the code. Please feel free to raise your queries.