Does This Python Binary Search Function Find the Element?

Binary Search (Bisection) in Python

Determining if an element is present in a sorted list or tuple is a common task in programming. While Python provides the bisect module for binary search, its bisect_left and bisect_right functions return a position even if the item is not found. To address this need, a Python implementation of binary search that explicitly returns a Boolean value is introduced.

Proposed Solution

The binary_search function takes a sorted list 'a', an element 'x' to search for, and optional starting and ending positions 'lo' and 'hi' for the search range. It uses the bisect_left function from the bisect module to locate the insertion point 'pos' for 'x' in the list 'a'.

If 'pos' is less than 'hi' and the element at 'pos' is equal to 'x', then 'x' is found, and 'pos' is returned as the index of its location in the list. However, if 'pos' reaches the end of the list (i.e., 'pos' equals 'hi'), 'x' is not found, and the function 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  # don't walk off the end

Example Usage

For instance, given a sorted list 'a' and an element 'x' to search for, the binary_search function can be used as follows:

result = binary_search(a, x)

if result == -1:
    print("Element not found")
else:
    print("Element found at index", result)

This concise Python function provides a convenient way to perform binary search for element existence checking in sorted lists while maintaining the simplicity and efficiency of binary search.

The above is the detailed content of Does This Python Binary Search Function Find the Element?. For more information, please follow other related articles on the PHP Chinese website!