Mainly Tech projects on Python and Electronic Design Automation.

Tuesday, April 20, 2010

Am I one of the 10% of programmers who can write a binary search?

I just read this post where the blogger read a passage in a book that stated that only 10% of programmers could write a binary search from the description. I read up to the description of the binary search algorithm given in the book then thought I would try and implement it without finishing the reading of the rest of his blog entry.

I took around half an hour to come up with the following:

'''
from: http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/
"Only 10% of programmers can write a binary search"

Binary search solves the problem [of searching within a pre-sorted
array] by keeping track of a range within the array in which T
[i.e. the sought value] must be if it is anywhere in the array.
Initially, the range is the entire array. The range is shrunk by
comparing its middle element to T and discarding half the range.
The process continues until T is discovered in the array, or until
the range in which it must lie is known to be empty. In an
N-element table, the search uses roughly log(2) N comparisons.

'''

def binsearch(data, item):
if not data:
return False
lo, hi = 0, len(data)-1
mid = (hi + lo) // 2
#print(lo,mid,hi)
while item != data[mid] and lo < hi:
lo, mid, hi = ( (lo, (lo + mid) // 2, mid)
if item < data[mid] else
(mid+1, (hi + mid + 1) // 2, hi) )
#print(lo,mid,hi)
#0/0
return item == data[mid]

if __name__ == '__main__':
for dlimit in range(5):
data = list(range(dlimit))
print(data)
for item in data:
assert binsearch(data, item)
for item in list(range(dlimit+1)):
print(item)
assert not binsearch(data, item - 0.5)

What happens with an empty list, and the little plus ones were added after I put in the assert statements, and I was satisfied enough to go on and complete the reading of the blog.

Extra Restrictions


The blog goes on to state that the rules of test are that no testing is to be done. A compiler can be used to ensure that their are no mechanical errors however.

Whoa! I was shocked and then secretly pleased. I use Python, and automatically added the tests as part of my development process. In no way did I think that I could do the task without passing some tests. I am still not saying that my implementation is correct, but I have tested for a lot of corner-cases such as:
  • Lists of length zero, one and more than one.
  • Items in every position of the list.
  • Items outside the list: less than, greater than and between all members of the list.
I of course assume that items are comparable, and that data is sorted and subscript-able.

All I can conclude is that if given the test and access to a compiler/interpreter of your choice then one should argue convincingly for testing any submission as you would never deign to submit any code as complete unless tested. If the testers remain unconvinced then it may be time to stick to your guns as you don't gain by lowering your standards, especially in an interview situation when you know that testing is right!

P.S. I have since had a look at the code of the Python bisect module and the algorithm given on Wikipedia, and they both seem more elegant than mine.

6 comments:

  1. Hehe had a little time this morning resolving this exercise.

    My solution is a bit long for what it does, but tests says it right till then. I will do a bit more later and then post it somewhere.

    Maybe it should return mid or None, to return the found (or not) index ?

    ReplyDelete
  2. This test is slightly different to what the Python module does. It only needs to check whether an item is a member of the sorted list, not return some index.

    I know it feels a little weird putting your code up for scrutiny in a case like this where only 10% were previously found worthy. If you have any extra checks and the reasons to add them then please state those too.

    Welcome.

    - Paddy.

    ReplyDelete
  3. I did just the same - wrote the code and tests, read the rest of the article and then thought "what, no testing allowed??"

    It was an enjoyable diversion whilst waiting for a big compile to take place - thanks!

    Martin

    ReplyDelete
  4. Respectfully, I'm not sure this test has any real meaning. A vital part of the SDLC is testing. The statement that 90% of developers can't code is misrepresentative of the actual experiment. Would you claim 90% of writers can't write if 90% of papers contained a typo in the unedited copies (which wasn't caught by spell-check)?

    ReplyDelete
  5. Hi id,
    SDLC?

    I am not the one who agrees with the test, if you read the entry above you will see that I too have my reservations.

    - paddy.

    ReplyDelete
  6. Sorry for the acronym.
    SDLC = Software Development Life Cycle

    ReplyDelete

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us

Blog Archive