Is there a binary search in Python?

Is there a binary search in Python?

I'm glad you asked! Yes, there are several ways to implement binary search in Python. In this answer, I'll cover the most common approaches.

The Classic Binary Search Algorithm

Before diving into Python-specific implementations, let's start with a brief overview of the classic binary search algorithm:

Given an array arr of size n, where all elements are unique and sorted in ascending order, find the index of a target value target.

This process continues until the target value is found or it's determined that the target value is not in the array (i.e., low > high).

Python Implementations

Now, let's explore Python-specific implementations of binary search:

You can implement a simple binary search algorithm using recursion:

def binary_search(arr, target):
low = 0
high = len(arr) - 1
def recursive_search(low, high):
if low > high:
return -1  # Not found
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return recursive_search(mid + 1, high)
else:
return recursive_search(low, mid - 1)
return recursive_search(low, high)

This implementation uses a recursive function to perform the search.

You can also implement an iterative binary search algorithm using a loop:

def binary_search(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:
low = mid + 1
else:
high = mid - 1
return -1  # Not found

This implementation uses a while loop to perform the search.

Python's built-in bisect module provides a more convenient way to implement binary search. The bisect_left and bisect_right functions can be used to find the insertion point of a target value in a sorted array.

import bisect
def binary_search(arr, target):
idx = bisect.bisect_left(arr, target)
if idx != len(arr) and arr[idx] == target:
return idx
return -1  # Not found

This implementation is concise and easy to use.

The performance of these implementations depends on the size of the input array and the target value. In general, the iterative implementation (Method 2) tends to be slightly faster than the recursive implementation (Method 1). The bisect module-based implementation (Method 3) is often the fastest, as it leverages CPython's optimized binary search algorithm.

In conclusion, Python provides various ways to implement binary search. Choose the approach that best suits your needs and constraints.

Python binary search api

Python Binary Search API

In this article, we will explore the concept of binary search and its implementation as a Python API. The binary_search API takes a sorted list and an item to find as inputs and returns the index of the item if it exists in the list or -1 if it does not.

What is Binary Search?

Binary search is a fast search algorithm that finds the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half until the target value is found. This algorithm has an average time complexity of O(log n), where n is the number of elements in the array.

Implementing Binary Search in Python

Here's the implementation of the binary search API using Python:

def binary_search(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:
low = mid + 1
else:
high = mid - 1
return -1

In the above implementation, we initialize two pointers: low and high. These pointers represent the search interval. We then calculate the midpoint of the search interval using the formula (low + high) // 2.

If the value at the midpoint is equal to the target, we return the index of the midpoint. If the value at the midpoint is less than the target, we update low to be the midpoint plus one. Otherwise, we update high to be the midpoint minus one.

We repeat this process until low is greater than high, which indicates that the target is not present in the list. In this case, we return -1.

Using the Binary Search API

To use the binary search API, you need to first create a sorted list of items. Here's an example:

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]

Then, call the binary_search function with the list and the target item as inputs:

result = binary_search(arr, 5)
print(result)  # Output: 4

In this example, the binary_search API returns 4, which is the index of the item 5 in the sorted list. If you call the function with a target that does not exist in the list, it will return -1.

Advantages and Limitations

The binary search algorithm has several advantages:

However, there are some limitations:

Conclusion

In this article, we have implemented a binary search API in Python and discussed its advantages and limitations. Binary search is an efficient algorithm for finding items in sorted lists, but it requires that the input list be sorted and can only be used on lists or arrays.