3
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thank you for the answer. All your suggestions were very helpful :) \$\endgroup\$ – cycloidistic Nov 16 '16 at 6:01
1
\$\begingroup\$

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.
    """
    ...
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer. I think you make some good points. During an interview how much of the docstring do you think I should write. Since I don't have much time it might be a bit difficult to write down everything you mentioned. Nonetheless, thanks again :) \$\endgroup\$ – cycloidistic Nov 16 '16 at 7:17
  • \$\begingroup\$ @cycloidistic Well all of it is pretty essential if you want to use the method. In this case I would probably leave out the raises because it is only the corner case if a is not actually list-like. This could be made clearer by using a different name than a as suggested in one of the other answers. \$\endgroup\$ – Graipher Nov 16 '16 at 7:27
  • \$\begingroup\$ Sure. I'll keep that in mind from now on. \$\endgroup\$ – cycloidistic Nov 16 '16 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.