Dark Mode On/Off
LAST UPDATED: AUGUST 12, 2021

# Python Program for Binary Search in Python

A binary search is a method of locating a certain element in a list. In this tutorial, we will perform a binary search operation to discover an element's index position in a list with two different methods.

## Binary Search - A basic Introduction

Binary search is the most popular program for searching. Let's say we have a thousand-element list and we need to get the index position of a specific entry. Using the binary search technique, we may quickly determine the index location of an element. To use the binary search method, the entries in the list must be sorted. If the components aren't already sorted, sort them first. To execute binary search we can follow two approaches which are discussed below:

1. Iterative Method

2. Recursive Method

We will discuss all these approaches in detail separately.

### Approach 1: Iterative Binary Searching Operation

In this method, we'll iterate through the entire list, repeating a series of instructions. We'll keep looking for the middle value until we've found it. Let's have a look at the Algorithm followed by code for better understanding:

### Algorithm

1. Create a function binary_search() which accepts 4 parameters(array, low, high, a).
2. Declare two variables to store the highest and the lowest values in the list.
3. Then Follow step 4 until the lowest and highest meet each other:
4. mid = (low + high)/2
if (a == arr[mid])
return mid
else if (a > arr[mid]) // a is on the right side
low = mid + 1
else // a is on the left side
high = mid - 1
5. Intialize the array and the element to be found
6. Print the resulting position if the element is found else print Not found.

### Program of Binary Search

As discussed above in the algorithm, let us now dive into the programming part of iterative binary search operation influenced by the algorithm.

``````def binary_search(arr, a, low, high):

# Repeat until low and high meet each other
while low <= high:

mid = low + (high - low)//2

if arr[mid] == a:
return mid

elif array[mid] < a:
low = mid + 1

else:
high = mid - 1

return -1

arr = [1, 2, 3, 4, 5, 6, 7]
a = 4
#printing the array
print("The given array is", arr)

#printing element to be found
print("Element to be found is ", a)

index = binary_search(arr, a, 0, len(arr)-1)

if index != -1:
print("The Index of the element is " + str(index))
else:

The given array is [1, 2, 3, 4, 5, 6, 7]
Element to be found is 4
The index of the element is 3

### Approach 2: Recursive Binary Search Operation

In the binary search, the recursion approach can be used. We'll create a recursive function that keeps calling itself until the condition is met. The recursive approach follows the divide and conquers method which is a method of resolving a complex issue by dividing it down into smaller sub-problems, solving them, and then combining them to get the desired result. Let's have a look at the Algorithm followed by code for better understanding:

### Algorithm

1. Create a function binary_search() which accepts 4 parameters(array, low, high, a).
2. Then Follow step 3 until the lowest and highest meet each other:
3. mid = (low + high) / 2
if a == arr[mid]
return mid
else if a > arr[mid] // a is on the right
return binary_eearch(arr, a, mid + 1, high)
else // a is on the right
return binary_search(arr, a, low, mid - 1)
4. Intialize the array and the element to be found
5. Print the resulting position if the element is found else print Not found.

### Program of Binary Search

As discussed above in the algorithm let us now dive into the programming part of recursive binary search operation influenced by the algorithm.

``````def binary_search(arr, a, low, high):

if high >= low:

mid = low + (high - low)//2

# If found at mid, then return it
if arr[mid] == a:
return mid

# Search the left half
elif arr[mid] > a:
return binary_search(arr, a, low, mid-1)

# Search the right half
else:
return binary_search(arr, a, mid + 1, high)

else:
return -1

# printing array and element to be found
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print("The array given is: ", arr)
a = 9
print("The element to be found is: ", a)

index = binary_search(arr, a, 0, len(arr)-1)

if index != -1:
print("Element is present at index " + str(index))
else:

The array given is: [1, 2, 3, 4, 5, 6, 7, 8, 9]
The element to be found is: 9
Element is present at index 8

### Conclusion

In this tutorial, we have seen two approaches to the binary search operation. The first approach is the iterative approach which is direct because in this method we'll keep looking for the middle value until we've found it. The second approach is a recursive method in which we'll create a recursive function that keeps calling itself until the condition is met.

Want to learn coding?
Try our new interactive courses.
Over 20,000+ students enrolled.