Binary search (bisection) in Python

bisect_left finds the first position p at which an element could be inserted in a given sorted range while maintaining the sorted order. That will be the position of x if x exists in the range. If p is the past-the-end position, x wasn't found. Otherwise, we can test to see if x is there to see if x was found.

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

Why not look at the code for bisect_left/right and adapt it to suit your purpose.

like this:

def binary_search(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        midval = a[mid]
        if midval < x:
            lo = mid+1
        elif midval > x: 
            hi = mid
        else:
            return mid
    return -1

This is a little off-topic (since Moe's answer seems complete to the OP's question), but it might be worth looking at the complexity for your whole procedure from end to end. If you're storing thing in a sorted lists (which is where a binary search would help), and then just checking for existence, you're incurring (worst-case, unless specified):

Sorted Lists

O( n log n) to initially create the list (if it's unsorted data. O(n), if it's sorted )
O( log n) lookups (this is the binary search part)
O( n ) insert / delete (might be O(1) or O(log n) average case, depending on your pattern)

Whereas with a set(), you're incurring

O(n) to create
O(1) lookup
O(1) insert / delete

The thing a sorted list really gets you are "next", "previous", and "ranges" (including inserting or deleting ranges), which are O(1) or O(|range|), given a starting index. If you aren't using those sorts of operations often, then storing as sets, and sorting for display might be a better deal overall. set() incurs very little additional overhead in python.

It might be worth mentioning that the bisect docs now provide searching examples: http://docs.python.org/library/bisect.html#searching-sorted-lists

(Raising ValueError instead of returning -1 or None is more pythonic – list.index() does it, for example. But of course you can adapt the examples to your needs.)

Simplest is to use bisect and check one position back to see if the item is there:

def binary_search(a,x,lo=0,hi=-1):
    i = bisect(a,x,lo,hi)
    if i == 0:
        return -1
    elif a[i-1] == x:
        return i-1
    else:
        return -1

Binary search (bisection) in Python

Related

Recent Posts