# 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):
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:
```rakesh@folio MINGW64 /e/python (master)