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:
    print("Element Not found")

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:
    print("Not found")

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.