How Can I Efficiently Implement a Binary Search in Python to Check for Item Existence?

Binary search (halo search) in Python

Python provides library functions to implement binary search (also called binary search), Used to find items in a sorted list or tuple. However, these functions still return a position if the item is not found.

To solve this problem and only detect if the item exists, one way is to use the bisect.bisect_left() function to find the insertion position and then check if the item at that position is equal to the target item. However, this can be tedious and also requires bounds checking when the number is larger than the largest number in the list.

Due to memory consumption, a dictionary is suggested as an alternative in the question. However, this may require approximately twice the memory requirements.

Therefore, this problem can be solved by implementing a binary search using custom code:

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 uses the bisect_left() function to find the insertion position, which indicates the position of the target item if it exists , or indicate a position that is out of range when it is not present. You can determine whether the target item exists by checking whether the item at that position is equal to the target item.

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