Since I got my copy of “Programming Pearls” by Jon Bentley, I have hardly been able to enjoy the excellent writing skills of Jon Bentley. I finally got some time to read, “Aha! Algorithms” from his book and I encountered a section on “Binary Search”. I read somewhere that during a lecture at CMU, Jon said that most binary search implementations were broken. After reading a description of the problem from the book, I decided to whip up an implementation myself. Binary search involves probing the range to see on which side of the median, the number lies and the new range is that half. This process is repeated until the value is located. So, here is a very short binary search I wrote:
if end< begin:
return "Number not found in list"
pos = (begin+end)/2
if num_list[pos] > num:
return search(num_list, num, begin, pos - 1)
elif num_list[pos] < num:
return search(num_list, num, pos+1, end)
else:
return pos
num_list = [1, 2, 4, 5, 6, 8, 11, 34, 72, 112, 134, 145, 156, 167, 178, 189, 190, 210, 321, 432, 543, 654, 765, 876, 987]
value = 112
print search(num_list, value, 0, len(num_list))
I ran the script and this is what I got:
python binsearch2.py 9
Another attempt:
value = 35
print search(num_list, value, 0, len(num_list))
The output:
python binsearch2.py Number not found in list
The next problem in the same chapter involved rotating vectors. A beautiful algorithm was described in the book. To rotate “i” elements out of “n” in an array, the best solution I could think of was to throw i elements in a separate list and keep appending them in reverse order to a new list which contains the (n-i) elements. As usual, Jon Bentley had a better algorithm. He considered the list to be two groups “a” and “b”. So our list can be represented by “ab”. We need to obtain “ba”. If we denote a’s reverse as and b’s reverse as
, then we get,
=
. So, I implemented this algorithm in a few seconds using:
”‘Rotate i elements of the given list’”
a = list_name[:i]
b = list_name[i:]
a.reverse()
b.reverse()
final_list = a+b
final_list.reverse()
return final_list
This is how it works:
The solution:
python vectorrot.py ['d', 'e', 'f', 'g', 'h', 'i', 'j', 'a', 'b', 'c',]
.
Well, there’s another problem that I shall solve later. The book is really a masterpiece. I had a sneak-peek at what was to follow the next problem and it turns out its an anagram constructor! Wee! I can foresee a fun filled week ahead!
EDIT: The binary search implementation now terminates when it can’t find the value in the list.
Comments 5
Yup. Jon Bentley is right: most binary search implementations are broken. Yours doesn’t terminate when the value sought isn’t in the list.
Posted 12 Jun 2008 at 10:21 am ¶@Ben,
Thanks for pointing it out. I have fixed it now and it seems to work.
Posted 12 Jun 2008 at 10:39 am ¶We used to have a saying when I was in college, “you can code FORTRAN in any language.” In this case, Jon Bentley’s code, while beautiful, elegant, fast, etc., is very C-oriented. Your example using .reverse() looks like a direct transliteration from C using strrev. Yes, it’s interesting, especially when designing optimal algorithms within the confines of C, but it is a poor way to teach yourself Python. Just like the elegance of C’s in-place of 2 integers or pointers, cleverly implemented as a C macro:
#define swap(a,b) (a)^=(b);(b)^=(a);(a)^=(b)
is much more clearly implemented using Python’s tuple assignment:
a,b = b,a
Here are two renditions of rotate using more Pythonic idioms (”idia”?), first using list slices, and second using iterators:
def rotate(list_name, i):
“”"Rotate i elements of the given list, using normal Python
list slicing”"”
return list_name[i:] + list_name[:i]
def iterrotate(list_name, i):
“”"Rotate i elements of the given list, using iterators so no
copies or slices are constructed”"”
retiter = iter(list_name)
ii = i if i >= 0 else len(list_name)+i
try:
while(ii):
retiter.next()
ii -= 1
except StopIteration:
pass
else:
for item in retiter:
yield item
retiter = iter(list_name)
ii = i if i >= 0 else len(list_name)+i
while(ii):
yield retiter.next()
ii -= 1
I’m sure the iterator-based solution has room for improvement, this is left as an exercise for the reader.
Of course, test cases on the boundaries are always useful, not just testing the nominal case:
def test(title,rotsize):
print “\n%s (%d)” % (title,rotsize)
print rotate(list(”abcdefghij”), rotsize)
for c in iterrotate(list(”abcdefghij”), rotsize):
print c,
print
test(”test rotation”, 3)
test(”test rotation size longer than list”, 50)
test(”test rotation size = list length”, 10)
test(”test zero rotation size”, 0)
test(”test negative sizes”, -4)
test(”test rotation size = -list length”, -10)
test(”test rotation size < -list length”, -15)
Prints:
test rotation (3)
['d', 'e', 'f', 'g', 'h', 'i', 'j', 'a', 'b', 'c']
d e f g h i j a b c
test rotation size longer than list (50)
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
a b c d e f g h i j
test rotation size = list length (10)
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
a b c d e f g h i j
test zero rotation size (0)
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
a b c d e f g h i j
test negative sizes (-4)
['g', 'h', 'i', 'j', 'a', 'b', 'c', 'd', 'e', 'f']
g h i j a b c d e f
test rotation size = -list length (-10)
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
a b c d e f g h i j
test rotation size < -list length (-15)
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
a b c d e f g h i j
(Your originally posted rotate() method passed all of these tests, too.)
As for binary search, check out the bisect module.
Cheers, and good luck at Purdue!
Posted 13 Jun 2008 at 6:33 pm ¶– Paul
Well, I agree I didn’t use any brain when I copied Jon’s implementation directly (the writing style is so cool that one can get carried away with ease), but thanks for such an excellent comment.
Did you go to Purdue CS as well?
Shriphani
Posted 14 Jun 2008 at 4:09 am ¶No, I studied Mechanical Engineering at RPI, the CS stuff came later. I’ve been very fortunate to have worked with a number of *very* smart CS folks, and some of it rubbed off on me.
Posted 17 Jun 2008 at 4:39 pm ¶Post a Comment