I ran across a blog post challenging people to write a binary search without actually running the code. The idea is to see what you can come up with without iteratively finding & fixing problems.
Given that I really like iteratively finding & fixing problems, this seemed a little bizarre at first. But the more I ponder it, the more I like the idea (at least as an exercise/toy/diversion). It reminds me of a programming class where we got a Java program on a printed sheet of paper, and had to write out what the outputs would be. It was really annoying, and I hated it, but I did definitely learn to think more clearly about code by doing these exercises. I hardly ever do anything like that anymore, and this little binary-search challenge was a nice refresher.
The post is the first in a series, and the whole set is really great reading. The "testing is not a substitute for thinking" part was especially good. I remember lots of times arguing that "the absence of errors is not evidence of correct behavior", which is one of his main points. Though he stated it more clearly, I think, as "Tests can only show the presence of bugs, not their absence".
So, here's the binary search I came up with. I've never run this code. It might have syntax errors. It might not work (though I think it probably does). I'll try some tests and see how it goes, but posting before actually trying it seemed most in line with the spirit of the challenge. I usually do Ruby these days, so I tried it in PHP just for fun.
* Returns either the array index of $needle in $haystack, or null.
* Assume: $haystack is a non-sparse, sorted, numerically indexed array.
*/
function binary_search( $needle, $haystack ) {
$left_idx = 0;
$right_idx = count( $haystack ) - 1;
if( $needle < $haystack[ $left_idx ] || $needle > $haystack[ $right_idx ] ) {
return null;
}
return recursive_binary_search( $needle, $haystack, $left_idx, $right_idx );
}
function recursive_binary_search( $needle, $haystack, $left_idx, $right_idx ) {
$midpoint_idx = floor( ($right_idx - $left_idx) / 2 ) + $left_idx;
$midpoint_val = $haystack[ $midpoint_idx ];
if( $midpoint_val == $needle ) {
return $midpoint_idx;
} else if ( $needle > $midpoint_val ) {
$next_left_idx = $midpoint_idx+1;
$next_right_idx = $right_idx;
} else {
$next_left_idx = $left_idx;
$next_right_idx = $midpoint_idx-1;
}
if( $next_left_idx > $next_right_idx ) {
return null;
}
return recursive_binary_search( $needle, $haystack, $next_left_idx, $next_right_idx );
}
I'm pretty sure I could make it shorter, more dense, etc. I think it's pretty readable this way, though.
