How Can I Efficiently Check for Item Presence in a Sorted List Using Binary Search in Python?

Binary Search (Bisection) in Python with Explicit Item Presence Check

The Python bisect module provides functions for performing binary search, such as bisect_left and bisect_right. However, these functions return a position even if the item being searched for is not present in the list. For cases where only the presence or absence of an item is desired, a more explicit check is required.

One approach is to use bisect_left and verify if the item at the returned position matches the target. However, this method introduces additional complexity, such as boundary checking for cases where the target is larger than the largest element in the list.

A simpler and more direct solution is to implement a custom binary search function that explicitly checks for the presence of the item before returning the result. Here's an example:

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  # don't walk off the end

This function takes a sorted list a, a target value x, and optional lower and upper bounds for the search. It uses bisect_left to find the insertion point for x, then checks if the item at that position matches the target. If a match is found, the function returns the position; otherwise, it returns -1 to indicate the item's absence.

By incorporating this explicit check, you can efficiently determine the presence or absence of an item in a sorted list without introducing unnecessary overhead or limitations.

The above is the detailed content of How Can I Efficiently Check for Item Presence in a Sorted List Using Binary Search in Python?. For more information, please follow other related articles on the PHP Chinese website!