A binary search in Python

This week, I received some exciting news by email: I will be interviewed for an internship at Microsoft! In order to keep my memory fresh, I have decided to practice my algorithms and data structures, then post the results.

To get things started, here is how you perform a binary search in Python, not that you should have to. This function will return the index of the given item in the given list.

countries = ("Afghanistan","Albania","Algeria", ...)

def bsearch(items, val, offset=0):
    index = int(len(items)/2)
    if val == items[index]:
        return index + offset
    elif(val > items[index]):
        return bsearch(items[index:], val, offset+index)
    else:
        return bsearch(items[:index], val, offset)

print bsearch(countries, "Central African Rep")

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax