# Binary search attempt

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


I'm afraid this code has a few bugs.

binsearch([], 1) throws an IndexError.

binsearch(, 1) goes into an infinite loop.

• if len(mylist) == 0: return 'undefined' elif len(mylist) == 1 and keyval == mylist: return 0 elif len(mylist) == 1 and keyval != mylist: return 'undefined' Sep 29, 2015 at 0:06
• added those lines of code right to the top to handle those errors thanks for the input mjolka Sep 29, 2015 at 0:06
• still curious on how to optimize my code, since binary searches are supposed to run very quickly Sep 29, 2015 at 0:07
• @user85519 I found another test case that fails: [0, 0, 1, 2], key = 1. I'd suggest having a look at the implementation here. Sep 29, 2015 at 2:19

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.