How Can I Efficiently Perform a True/False Binary Search in Python?

Binary Search in Python: Improved Approach

In Python, binary search is effortlessly performed through the bisect module. However, if a precise indication of an item's existence within a list is desired, the bisect_left and bisect_right functions may not suffice.

To address this need, Python libraries do not offer a dedicated function tailored solely for binary search with an explicit True/False output. Consequently, a custom solution is required.

The following snippet defines the binary_search function, which performs binary search on a sorted list a and returns the index of the target item x if found. If x is not present, it returns -1:

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):
    if hi is None: hi = len(a)
    pos = bisect_left(a, x, lo, hi)  # Find insertion position
    return pos if pos != hi and a[pos] == x else -1  # Check if x is there

This function utilizes bisect_left to determine the insertion point for x. If x is present in the list, it will be located at this insertion point. To confirm this, the value at the insertion point is compared to x. If they match, x was found, and its index is returned. Otherwise, x is not present, and -1 is returned to indicate this.

This custom function provides a concise and efficient solution for performing binary search with a clear True/False indication of an item's presence within a list, fulfilling the need identified in the original question.

The above is the detailed content of How Can I Efficiently Perform a True/False Binary Search in Python?. For more information, please follow other related articles on the PHP Chinese website!