More on binary search

I wrote this post: Am I one of the 10% of programmers who can write a binary search? as a reply to: Are you one of the 10% of programmers who can write a binary search? by Mike Taylor.

Since then, Mike has followed up with this: Testing is not a substitute for thinking which starts as a summary of the responses to the earlier post then moves on to his own views on testing.

There is mention of some great work by Darius Bacon who tests around twenty solutions gathered, painstakingly, from the comments. Darius' program is great work, but I thought that my testing strategy might be better so modified his code to:

1. Add my attempt as function: paddy3118
2. Graft on a version of my test routine to his list of function variants

The delta code was added to the end and looks like the following:

def paddy3118(data, item):
   if not data:
       return -1
   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 mid if item == data[mid] else -1
# PASSES test()
#test(paddy3118)

#print sorted(k for k,v in globals().items() if type(v)==type(dan) and 'test' not in k)
tests = (Max, aaron_maxwell, ashish_yadav, ben_gutierrez, clark,
        dan, dave_r, ed_marshall, guilherme_melo, jasper, martin,
        michael_fogleman, paddy3118, patrick_shields, paul,
        rodrigo_b, scott, si, tomas_henriquez,
        travis_wrapped, yc)

if __name__ == '__main__':
   totpass = 0
   for t in tests:
       fails =0
       for dlimit in range(5):
           data = list(range(dlimit))
           for item in data:
               try:
                   assert t(data, item) != -1
               except:
                   fails += 1
                   print("  ERROR: %s FAIL when looking for %i in %r" %
                         (t.func_name, item, data))
                   break
           for item in list(range(dlimit+1)):
               try:
                   assert t(data, item - 0.5) == -1
               except:
                   fails += 1
                   print("  ERROR: %s FAIL as %3.1f is found in %r" %
                         (t.func_name, item - 0.5, data))
                   break
           if fails:
               break
       if not fails:
           totpass += 1
           print('PASS: %s' % t.func_name)
   print("\n%i/%i = %3.1f%% of functions pass" %
         (totpass, len(tests), 100 * totpass / float(len(tests))))
   '''
    PASS: Max
      ERROR: aaron_maxwell FAIL as -0.5 is found in []
    PASS: ashish_yadav
    PASS: ben_gutierrez
      ERROR: clark FAIL when looking for 0 in [0]
      ERROR: dan FAIL as -0.5 is found in []
      ERROR: dave_r FAIL as -0.5 is found in []
      ERROR: ed_marshall FAIL as -0.5 is found in []
      ERROR: guilherme_melo FAIL as -0.5 is found in []
      ERROR: jasper FAIL as -0.5 is found in []
      ERROR: martin FAIL as -0.5 is found in []
    PASS: michael_fogleman
    PASS: paddy3118
      ERROR: patrick_shields FAIL as -0.5 is found in []
    PASS: paul
      ERROR: rodrigo_b FAIL as -0.5 is found in []
      ERROR: scott FAIL as 1.5 is found in [0, 1, 2]
    PASS: si
      ERROR: tomas_henriquez FAIL when looking for 0 in [0, 1]
      ERROR: tomas_henriquez FAIL as 1.5 is found in [0, 1]
      ERROR: travis_wrapped FAIL when looking for 0 in [0]
    PASS: yc

    8/21 = 38.1% of functions pass
    '''

I find that i cannot agree with a lot of Mikes writing on test driven development as he seems to take an extreme position by separating test from development too much.
When I was creating my function, i new that there were likely to be issues with off-by-ones when modifying range indices, and with handling of an empty data list. I chose to leave a 'mental place-holder' on the off-by-one issues as I thought i could easily write tests to exercise those corners and fill them in. The alternative would be to mentally interpret those corner cases to write them down in 'development', then still have to thoroughly test for them anyway.

When writing my tests:

• I thought about the division of the range of the indices- and thought that I should use data of both odd and even lengths, and of sufficient length so that a range might be divided more than one.
• I thought about all the comparisons - and decided to test for every item that is in the data.
• I thought about the significant ways that an item might not be in the data - and decided to test for items between each and every data item, an items below the smallest and above the largest data items.

My paddy3118 function passed the Darius tests. My test routine failed the guilherme_melo test that was passed by Darius.

The only conclusion I can bring, is that you need to do some white box testing, i.e. tests based on knowledge of the code too. Mike Taylor needs to recognise that imposing rigid categories might well lead to extremes. I guess, their is no substitute for experience, but the unexperienced need to be given rules until they can learn enough to break them - Do we teach testing up front? Or not? (Remembering that given half a chance, testing by the novice will be inadequate).

- Paddy.

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.

The Securities and Exchange Commission is to mandate the use of Python?

Read on

Smartphone Programming, Compare and Contrast

• Apple: Steve Jobs Has Just Gone Mad
• Android: Android Scripting Environment brings scripting languages to Android.
• Nokia: Python for S60

Do you still want that Ipad?