# Python Program for Binary Search

Python Program for Binary Search; Through this tutorial, we would love to show you how to implement a program to binary search in python.

Binary Search is applied on the sorted array or list of large size. It’s time complexity of O(log n) makes it very fast as compared to other sorting algorithms. To use binary search on a collection, the collection must first be sorted.

## Python Program for Binary Search

• Python Program for Binary Search with Function
• Python program for binary search using recursion function

### Algorithm of Binary Search

Implement binary search following the below steps:

• If the target value is equal to the middle element of the array, then return the index of the middle element.
• Otherwise, compare the middle element with the target value,
• If the target value is greater than the number in the middle index, then pick the elements to the right of the middle index, and start with Step 1.
• If the target value is less than the number in the middle index, then pick the elements to the left of the middle index, and start with Step 1.
2. If a match is found, return the index of the element matched.
3. Otherwise, return `-1`

### Python Program for Binary Search with Function

```# Binary search function
def binarySearchAlgo(xlist, key):

a = 0
b = len(xlist)
while a < b:
c = (a + b)//2
if xlist[c] > key:
b = c
elif xlist[c] < key:
a = c + 1
else:
return c
return -1

# input a list of elements
xlist = input('Enter the sorted list of numbers: ')

#split a element
xlist = xlist.split()
xlist = [int(x) for x in xlist]

# search for in list
key = int(input('The number to search for: '))

# call binary search function
index = binarySearchAlgo(xlist, key)
if index < 0:
else:
print('{} was found at index {}.'.format(key, index))
```

After executing the program, the output will be:

```Enter the sorted list of numbers:  1 2 3 4 5 6 7 8 9
The number to search for:  8
8 was found at index 7.```

### Python program for binary search using recursion function

```# Python code for recursive binary search

# Returns index of key in xlist if present, else -1
def binarySearch (arr, l, r, x):

# Check base case
if r >= l:

mid = l + (r - l)//2

# If element is present at the middle itself
if arr[mid] == x:
return mid

# If element is smaller than mid, find in left sub array
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)

# Otherwise find the element in right subarray
else:
return binarySearch(arr, mid+1, r, x)

else:
# Element is not present in the list
return -1

# input a list of elements
xlist = input('Enter the sorted list of numbers: ')

#split a element
xlist = xlist.split()
xlist = [int(x) for x in xlist]

# search for in list
key = int(input('The number to search for: '))

# Function call
result = binarySearch(xlist, 0, len(xlist)-1, key)

if result != -1:
print('{} was found at index {}.'.format(key, result))
else:

```

After executing the program, the output will be:

```Enter the sorted list of numbers:  1 2 3 4 5 6 7 8
The number to search for:  6
6 was found at index 5.```