Binary search a sorted list of integers

Question

This code is meant to do a binary search of a sorted list containing integers.

I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.

def bin_search(a, item):
    first = 0
    last = len(a) - 1
    found = False

    while first <= last and not found:
        mid = (first + last) // 2
        if a[mid] == item:
            found = True
        else:
            if item < a[mid]:
                last = mid - 1
            else:
                first = mid + 1

    return found

Answer 1

Looks pretty good to me. Personally, I would get rid of the found variable and just return True if item is found.

I would also use a more descriptive name for the list. a just doesn't say list to me. If you want to keep it short, use something like l or borrow Haskell's convention and use something like as or xs.

Finally, if you wanted, you could use an if/elif/else instead of the if/else with nested if/else inside. But I can't think of any compelling reason to do so.

As an answer to an interview question, I think you'll want to do a better job of indicating coverage of the case where the list is empty. Your code covers this case perfectly (last will be -1 and first will be 0, so first <= last is False), but it's not obvious. So it probably wouldn't hurt to add an explicit check or add a comment with a brief explanation why that case is covered. Then there's no doubt that you considered that case.

Answer 2

For an interview question I would change two more things:

1. Use tuple assignment, first, last = 0, len(a) - 1

2. Add a descriptive docstring to describe what the function does and what it's parameters are:

def bin_search(a, item):
    """
    Binary search for an item in a sorted list.

    Args:
        a:     A sorted list
        item:  The item to search for
    Returns:
        True or False
    Raises:
        IndexError if a is not indexable

    If a has length zero, always returns False.
    """
    ...