Binary search algorithm in python

Solution 1:

It would be much better to work with a lower and upper indexes as Lasse V. Karlsen was suggesting in a comment to the question.

This would be the code:

def binary_search(array, target):
    lower = 0
    upper = len(array)
    while lower < upper:   # use < instead of <=
        x = lower + (upper - lower) // 2
        val = array[x]
        if target == val:
            return x
        elif target > val:
            if lower == x:   # these two are the actual lines
                break        # you're looking for
            lower = x
        elif target < val:
            upper = x

• lower < upper will stop once you have reached the smaller number (from the left side)
• if lower == x: break will stop once you've reached the higher number (from the right side)

Example:

>>> binary_search([1,5,8,10], 5)   # return 1
1
>>> binary_search([1,5,8,10], 0)   # return None
>>> binary_search([1,5,8,10], 15)  # return None

Solution 2:

Why not use the bisect module? It should do the job you need---less code for you to maintain and test.