Binary Search Program in Python

Binary Search Program in Python. Binary search is an efficient algorithm for finding an item from a sorted list or array of items. Sometimes it is also known as half-interval search, logarithmic search, or binary chop. 

Condition to use binary search:- The array must be sorted.

The binary search algorithm cannot be applied to unsorted arrays. This algorithm can be used when the array has terms occurring in order of increasing size (for instance: if the terms are numbers, they are listed from smallest to largest; if they are words, they are listed in lexicographic, or alphabetic, order). If the array or list is not sorted then before applying the binary search algorithm, first sort the array or list.

The binary search algorithm can be written in two ways. These are,
a) Recursive approach
b) Iterative approach


Binary Search in Python using Recursion

In the recursive approach, the recursion technique is used. It is an example of the divide and conquers technique where bigger problems are divided into smaller problems. Like all divide and conquer algorithms binary search first divides the large array into smaller sub-arrays and then solves it recursively.  Let us see it in detail.

Binary Search Algorithm in Python using Recursive Approach

a) Take an array, initial index, size, and search key.
b) Find the middle term.
c) if middle term == search key then return index.
d) if middle term > search key then apply recursive call on the first half of the array.
e) else apply a recursive call on the second half of the array.
f) Repeat the process until the search key is not matched.
g) If not matched then return -1.

The binary search method in Python using recursion can be written as,

def BinarySearch(arr, low, high, key):
    if high >= low:
        mid = (high + low) // 2
        if (arr[mid] == key):
            return mid
        elif (arr[mid] > key):
            return BinarySearch(arr, low, mid - 1, key)
        else:
            return BinarySearch(arr, mid + 1, high, key)
    else:
        return -1

The time complexity of this algorithm = O(log n)

How Recursive approach works?

In binary search using a recursive approach, we split the array from the middle into two subarrays of the same size or where one of these smaller lists has one fewer term than the other. Let us understand it through an example.

Array = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};

Example

Assume the search term = 40. Then the steps in binary search,

  • Find the middle term of the array. If the size of the array is odd then middle-index = (size – 1)/2 else middle-index = size/2. In our example, middle index = 10/2 = 5, and middle term is array[3] = 60
  • Compare the middle term and search term. If the middle term > search term then it may exist in the first portion of the array else in the second portion of the array. Since 60 > 40 therefore search terms may exist only in the first portion of the array.
  • Split the array into two parts from the middle index. The subarr1 = {10, 20, 30, 40, 50} and subarr2 = {60, 70, 80, 90, 100}.
  • Since the array is sorted and 60 > 40, therefore search terms may exist only in the first sub-array. Forgot about the second sub-array, no use of it, only the first sub-array is required for the next step. Now, assume the original array = {10, 20, 30, 40, 50}, and search term = 40.
  • Repeat the same process with the first sub-array. Find the middle term. The middle index = (5-1)/2 = 2, middle term is array[2] = 30
  • Compare middle term with a search term, 30 < 40 therefore it may exist only in the second portion.
  • Split array into two subarrays from the middle index. The new sub arrays are:- subarr1 = {10, 20} and subarr2 = {30, 40, 50}. Only subarr2 will be considered for the next steps, no use of subarr1. Now, assume array = {30, 40, 50} and search term = 40. Repeat the process.
  • Find the middle term. The middle index = (3-1)/2 = 1 and the middle term is array[1] = 40.
  • Compare the middle term and search term. Currently, both are equal and a match is found.

Python Program to implement binary search using Recursion

Now let us see the implementation of binary search algorithms in Python. Here the function binarySearch() finds the index of the search key, if the match is found then it returns the index of the search key else it returns -1.

# Python program for binary search using recursion

def BinarySearch(arr, low, high, key):  #user-defined function
    if high >= low:  #check base case
        mid = (high + low) // 2
        if (arr[mid] == key):
            return mid
        elif (arr[mid] > key):
            return BinarySearch(arr, low, mid - 1, key)
        else:
            return BinarySearch(arr, mid + 1, high, key)
    else:
        return -1

arr = [ 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 ]  #array
key = 40  #search key

# calling function
result = BinarySearch(arr, 0, len(arr)-1, key)

# display result
if result != -1:
    print(key, "Found at index", str(result))
else:
    print(key, "not Found")

Output:-

40 Found at index 3


Binary Search in Python using Iterative approach

In this approach, instead of calling the method recursively, we use iteration to traverse the array and find the search key. Both approaches are quite the same, with two differences in implementation. 

In a recursive method, there is no loop, and rather than passing the new values to the next iteration of the loop, it passes them to the next recursion. In the iterative method, the iterations can be controlled through the looping conditions, while in the recursive method, the maximum and minimum are used as the boundary condition. 

Algorithm

To search for the integer x in the list/array a1, a2 , … ,an , where array is in ascending order (a1 < a2 <  ··· < an)

  • begin by comparing x with the middle term am of the list/array, where m = ⌊(n + 1)/2⌋. 
  • If x > am, the search for x is restricted to the second half of the list, which is am+1, am+2, …, an.
  • If x is not greater than am, the search for x is restricted to the first half of the list, which is a1, a2, …, am.
  • The search has now been restricted to a list with no more than ⌊n/2⌋ elements. 
  • Using the same procedure, compare x to the middle term of the restricted list. 
  • Then restrict the search to the first or second half of the list. 
  • Repeat this process until a list with one term is obtained. 
  • Then determine whether this term is x.

In Python, the algorithm can be written as,

def BinarySearch(arr, key):
    low = 0
    high = len(arr) - 1
    mid = 0
 
    while low <= high:
        mid = (high + low) // 2
        if arr[mid] < key:
            low = mid + 1
        elif arr[mid] > key:
            high = mid - 1
        else:
            return mid
    return -1

Python Program

Python program for binary search using iterative approach,

# Python program for binary search using recursion

def BinarySearch(arr, key):  #user-defined function
    low = 0
    high = len(arr) - 1
    mid = 0
 
    while low <= high:
        mid = (high + low) // 2
        if arr[mid] < key:
            low = mid + 1
        elif arr[mid] > key:
            high = mid - 1
        else:
            return mid
    return -1

arr = [ 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 ]  #array
key = int(input('Enter search key: '))  #search key

# calling function
result = BinarySearch(arr, key)

# display result
if result != -1:
    print(key, "Found at index", str(result))
else:
    print(key, "not Found")

Output:-

Enter search key: 10
10 Found at index 0

Enter search key: 60
60 Found at index 5


Binary Search (bisect) in Python

This python program will use a module, which provides support for maintaining a list in sorted order without having to sort the list after each insertion. This module name is bisect, because it uses a basic bisection algorithm. For long lists of items with expensive comparison operations, this can be an improvement over the more common approach.

Finding First Occurrence of an Element

The function bisect.bisect_left(arr, key, lo = 0, hi = len(arr)) is used to return the leftmost insertion point of key in a sorted list. The last two parameters are optional in this case, they are used to search in the sublist.

# Finding first occurrence of an element

from bisect import bisect_left 

def BinarySearch(arr, key): 
    i = bisect_left(arr, key) 
    if i != len(arr) and arr[i] == key: 
        return i 
    else: 
        return -1

arr  = [5, 10, 15, 15, 60]   #array
key = int(15)   #search key

index = BinarySearch(arr, key) #calling function

# display result
if index == -1: 
    print(key, "is absent") 
else:
    print("First occurrence of", key, "is present at", index) 

Output:-

First occurrence of 15 is present at 2

Finding Greatest Value Which is Smaller than key

The function bisect.bisect_left(arr, key, lo = 0, hi = len(arr)) is used to get the greater value, which is smaller than the key.

# Finding greatest value smaller than key

from bisect import bisect_left 
  
def BinarySearch(arr, key): 
    i = bisect_left(arr, key) 
    if i: 
        return (i-1) 
    else: 
        return -1
  
arr  = [5, 10, 15, 15, 60]   #array
key = int(50)   #search key

index = BinarySearch(arr, key) #calling function

# display result
if index == -1: 
    print("No value smaller than", key)
else: 
    print("Largest value, smaller than", key, "is at index", index) 

Output:-

Largest value, smaller than 50 is at index 3

Find Rightmost Occurrence of key

The function bisect.bisect_right(arr, key, lo = 0, hi = len(arr)) is used to return the rightmost insertion point of key in a sorted list arr. The last two parameters are optional in this case, they are used to search in the sublist.

# Finding rightmost occurrence of key

from bisect import bisect_right
  
def BinarySearch(arr, key): 
    i = bisect_right(arr, key) 
    if i != len(arr)+1 and arr[i-1] == key: 
        return (i-1) 
    else: 
        return -1
  
arr  = [5, 10, 15, 15, 60]   #array
key = int(15)   #search key

index = BinarySearch(arr, key) #calling function

# display result
if index == -1: 
    print(key, "is absent") 
else: 
    print("Last occurrence of", key, "is present at", index)

Output:-

Last occurrence of 15 is present at 3


Binary Search Time Complexity

Best-case
time complexity 
O(1)When the search key is present at the center
(middle term) of the array/list.
Worst-case
time complexity
O(log n)When a search key is not available or at
the extremity of the list.

In the iterative method, the space complexity would be O(1). While in the recursive method, the space complexity would be O(log n). 

For the small arrays linear search algorithm gives better performance compared to the binary array, but for the large arrays if the array is in sorted order then the binary search gives better performance compared to the linear search. 

There are specialized data structures designed for fast searching, such as hash tables, that can be searched more efficiently than binary search. However, binary search can be used to solve a wider range of problems, such as finding the next-smallest or next-largest element in the array relative to the target even if it is absent from the array.

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or you find anything incorrect? Let us know in the comments. Thank you!

Leave a Comment

Your email address will not be published. Required fields are marked *