# Binary search a sorted list of integers

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


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.

• Thank you for the answer. All your suggestions were very helpful :) Nov 16, 2016 at 6:01

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.
"""
...

• 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 :) Nov 16, 2016 at 7:17
• @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. Nov 16, 2016 at 7:27
• Sure. I'll keep that in mind from now on. Nov 16, 2016 at 7:38