Algorithms

Implementing Binary Search

This afternoon, I was reading a chapter in "Beautiful Code" (check it out at Amazon). There was a reference to the binary search algorithm presented in Jon Bentley's book "Programming Pearls" (see Amazon), accompanied by the challenge to write a correct implementation of the algorithm. To quote from Bentley:

Most programmers think that with the above description [of the algorithm] in hand, writing the code is easy. They are wrong. The only way to believe this is by putting down this column right now and writing the code yourself. Try it.

I tried it.