3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Please don't invalidate answers by editing your code. \$\endgroup\$ – Ethan Bierlein Sep 29 '15 at 0:17
1
\$\begingroup\$

I'm afraid this code has a few bugs.

binsearch([], 1) throws an IndexError.

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

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

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.