Binary search attempt

Question

I've heard about the binary search in an intro class I took a couple months ago, remembered how it worked and read this article, so I attempted to write my first binary search in Python. It works, but when I look at other people's attempts in the article, their code looks cleaner and a bit different.

My two main questions are:

1. What can I do to optimize my code from here?
2. Am I even performing a true binary search?

def binsearch(mylist, keyval):
large = len(mylist)-1
small = 0
temp = (len(mylist)-1)/2
key = 'undefined'
flag = 0
while flag == 0:
    if mylist[small] == keyval:
        key = small
        flag = 1
    elif mylist[large] == keyval:
        key = large
        flag = 1
    elif mylist[temp] == keyval:
        key = temp
        flag = 1
    elif temp + 1 == large or temp -1 == small:
        flag = 1
    if keyval > mylist[temp]:
        small = temp
        temp = small + (large - small)/2
    elif keyval < mylist[temp]:
        large = temp
        temp = temp - (large-small)/2
return key

Answer 1

I'm afraid this code has a few bugs.

binsearch([], 1) throws an IndexError.

binsearch([2], 1) goes into an infinite loop.

Answer 2

You have complicated the neatness of the binary search somewhat, but it is an honest attempt. However here are some comments to your code:

• Too many variables – There is no need for the flag and the key variable, they are only adding to the confusion. Instead it would be better to use a mid variable, and use this a little more
• Avoid flag variables – In most cases instead of using a flag variable like you have done, you could have a while True: loop, and then use break to get out of it. In this particular case it is even better to use a while small <= large: loop...
• In addition most of the comment by Curt F in his answer applies to your code as well :-)

Taking all of these into account, here is a new variant, rather heavily modified from your original code:

def binary_search(my_list, key):
    assert my_list == sorted(my_list)

    large = len(my_list) -1
    small = 0

    while (small <= large):
        mid = (small + large) // 2 )
        # print small, mid, large, " - ", my_list[mid], "~", key
        if my_list[mid] < key:
            small = mid + 1
        elif my_list[mid] > key:
            large = mid - 1
        else:
            return mid

    raise ValueError

This code is tested rather heavily, and should work nicely. It's rather similar to code from Wikipedia's binary search algorithm.