Binary search bisection in python

Binary search is a popular algorithm used to search for a specific element in a sorted list or array. It works by repeatedly dividing the search space in half until the target element is found or the search space is empty.

Option 1: Recursive Implementation

One way to implement binary search in Python is by using a recursive approach. Here’s a sample code:


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

In this implementation, the function takes an array, target element, and the low and high indices of the search space as parameters. It checks if the search space is empty (low > high) and returns -1 if it is. Otherwise, it calculates the middle index and compares the element at that index with the target. If they are equal, it returns the index. If the element is greater than the target, it recursively calls the function with the updated high index as mid – 1. If the element is smaller, it recursively calls the function with the updated low index as mid + 1.

Option 2: Iterative Implementation

Another way to implement binary search is by using an iterative approach. Here’s a sample code:


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

In this implementation, the function initializes the low and high indices to the start and end of the search space, respectively. It then enters a while loop that continues until the search space is empty (low > high). Inside the loop, it calculates the middle index and compares the element at that index with the target. If they are equal, it returns the index. If the element is greater than the target, it updates the high index to mid – 1. If the element is smaller, it updates the low index to mid + 1. If the loop exits without finding the target, it returns -1.

Option 3: Built-in bisect module

Python provides a built-in module called bisect that can be used to perform binary search on sorted lists. Here’s a sample code:


import bisect

def binary_search_bisect(arr, target):
    index = bisect.bisect_left(arr, target)
    
    if index < len(arr) and arr[index] == target:
        return index
    
    return -1

In this implementation, the bisect_left function from the bisect module is used to find the index where the target element should be inserted in the sorted list. If the index is within the bounds of the list and the element at that index is equal to the target, it returns the index. Otherwise, it returns -1.

Among the three options, the iterative implementation (Option 2) is generally considered the better choice. It is more efficient in terms of both time and space complexity compared to the recursive implementation (Option 1). The built-in bisect module (Option 3) is also a good choice if you are working with sorted lists and want a simpler and more concise solution.

Rate this post

6 Responses

    1. Sorry, but I have to disagree. Option 3 may work for you, but I find the bisect module cumbersome and unnecessary. I prefer sticking to the basics and keeping my code clean. Different strokes for different folks, I guess. #PythonDebate

Leave a Reply

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

Table of Contents