To be precise, the post says that only 10% of programmers can write it correctly without testing. I agree that this is an interesting statistic, however the industry has been deprecating implementing an entire algorithm in one go in favour of implementing algorithms incrementally.
Were I to write it without testing I would probably write it incrementally and try to perform the testing in my head as I went along. It feels very retrograde to try to write the whole thing out and only then start thinking about off-by-one errors, computer arithmetic issues, and other edge cases.
Short answer: Yes, I am, including without testing.<p>For several years I ran a challenge for exactly this question. I have a test harness and test suite, and would run people's programs through it. Roughly 1 in 30 or 40 of those submitted without testing (self-certified) would pass all the tests. Those who tested before submission passed about 1 time in 3.<p>The vitriol heaped on me was quite unbelievable, and in one case led to concerns for my physical safety. People who had decided to try the challenge then rounded on me and said it was unfair, unreasonable and unrealistic. I didn't affect the results - the vast, <i>vast</i> majority of people simply could not write a binary search that passed my test suite.<p>FWIW, my first attempt had exactly one problem, to the best of my knowledge. I decided to derive my code formally from the specification. The mistake concerned computer arithmetic, not the algorithm, and was the one lunk to from the article.<p>But my background is unusual.
No incremental testing strikes me as a rather valueless constraint. Small experiments are one of the most crucial skills -- if not <i>the</i> crucial skill -- in writing correct code. It's like asking me to swim with one arm tied behind my back to see if I am a good swimmer.<p>Sure, I can run these 'tests' on scratch paper or even in my head, if you require me to. But real life never requires this. I prefer to prove to myself that each piece of an algorithm is correct--using a combination of reasoning and microtesting--before moving on to the next. Why would I waste attention doing this all in my head? The computer will do many pieces of it for me quickly, accurately, in a way that catches language idiosyncracies, and most importantly frees my attention for considering more abstract errors.<p>Edit: I had to try anyway, and (as far as I can tell) I <i>was</i> able to do it correctly in about three minutes. But I suspect it has less to do with native programming ability and more to do with having written dozens of variants on binary searches in the past year (I've had reason to want to handle various types of fuzzy matches, filtering and desired multiplicities in return values). FWIW, even after a fairly exhaustive suite of random input tests, I trust this binary search I have just written far less than the many I've recently written using my usual incremental methodology. Were I to include this in an actual release, I would not attempt to prove what I just wrote correct. I would destroy it and do the job properly from scratch.<p>Which rather underscores my point. I just wrote some code the wrong way, and even in spite of quite a lot of recent domain experience, a pretty good test suite, and a lot of staring at it and thinking about it . . . <i>I don't trust it because I didn't test the pieces while I was writing it</i>.
I've written binary search for production code (Delphi RTL generic collections), and gotten it right, but more embarrassingly, I also wrote quick-sort and got it wrong. It was a mishmash of two strategies IIRC - a straight recursive quick-sort, and a half-inlined version with a loop, and it didn't work at all. Escaped into the wild owing to time crunch and me electing to do squeeze too many things in at the last moment.
<i>NO TESTING until after you’ve decided your program is correct.</i><p>Why? What is there to be gained by asking programmers to abide by such an unnatural constraint? I would never "decide my program is correct" without having tested at least bits and pieces of it in the REPL.
Nearly All Binary Searches and Mergesorts are Broken:
<a href="http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html" rel="nofollow">http://googleresearch.blogspot.com/2006/06/extra-extra-read-...</a>
> One of the reasons I’d like to see a copy of the Second Edition is to see whether this passage has changed<p>For the author: it hasn't changed. Still only 10%.<p>I actually had to write this binary search algorithm in my technical competency interview for my current job. Rather than hours, I had minutes and the extra gotcha was that it was unsorted data so I had to write quicksort first. I remember feeling excited that I was going to be working for a company that had such low level issues but eight months in it's still the only time I've written my own sort or search methods since University :)
A friend of mine once did work in C++ for the DoD. There was a logistics application that used Binary Search, which had a bug he was working on -- lots of items were somehow "misplaced" in the system. Eventually, he discovered that there was no guarantee that the list being searched was <i>sorted</i>!<p>As for writing out whole C programs and getting it right without debugging -- I once wrote a bit-banging controller for a model aircraft. We did bit-banging with a Gumstix board, which would let us use GPIO to implement 9 PWM inputs and 9 or 10 PWM outputs in software. I wrote a bit-banging loop that did all of the inputs and outputs and let programmers define control mixing functions and finite state machines.<p>I was unable to test it, because you can only test something like this by attaching to the hardware. Well, <i>it worked the first time and it can run the remote control of a model aircraft in flight</i>. (There was one tweak later, to eliminate some jitter in one of the PWM outputs, but that was just a refinement of function. It <i>just worked</i>.)
I wrote my version in PHP, wondering if someone could tell me what I did wrong (I didn't test it, I assume there are mistakes).<p><pre><code> <?php
function bsearch($search, $array, $start, $end){
//$start cannot be zero.
//$search not in $array
if($start>$end){
return -1;
}
//calculate middle
$middle = $start + ceil(($end-$start)/2);
//check match
if($array[$middle]==$search){
return $middle;
}
//is the middle higher than the search, if so, cut top
else if($array[$middle]>$search){
return bsearch($search, $array, $start, $middle-1);
}
//otherwise cut bottom
else{
return bsearch($search, $array, $middle+1, $end);
}
}
?></code></pre>
Yay, I did it in 20 minutes and even remembered to test for the empty array :-)<p>It <i>was</i> kind of stressful to have to pass 13 testcases on the very first attempt. I rigged them to just shout "YOU FAIL" at me without telling the specific place. Reread the code for one last time and ran it. After it completed without printing anything, I stared at the screen for like ten seconds, then went and changed one testcase to deliberately fail in case I'd screwed up the printing. Nope - everything went better than expected :-)<p>But Raganwald is right, this exercise doesn't really tell anything about my programming skill. I mean, I don't work like that at all. My first attempts are <i>always</i> broken. Iterating is faster (or maybe only feels faster) than trying to get the first attempt right.
I remember reading the linked post on the Google blog. Ah, here it is: <a href="http://news.ycombinator.com/item?id=1130463" rel="nofollow">http://news.ycombinator.com/item?id=1130463</a> (Wow, that was only 60 days ago?)<p>Maybe that's why when I did this in C just now, my version ended up almost identical to the Java version. (Mine does the more correct "int middle = low + (high - low) / 2;", and I wasn't even thinking about the possibility of integer overflow the other way.) So yes, but only from benefit of having to have written it numerous times in school and in teaching newbies to use it.
I started writing a solution and then stopped partway through because the pressure of getting it right in one shot was incredibly stressful.<p>If this were given to me for an interview question, I'd be incredibly meticulous and build a series of algorithms for len=0, len=1, len=2, etc., including various permutations of values, until I establish a general solution, which I would then submit for the final answer.<p>I would hardly ever do that in actual coding, though, because I could rely on hammering it with tests instead.
Side-issue: why isn't Golden section better known ?<p>Luenberger's book [1] convinced me that a line search should be done with golden section, when I was hacking non-linear optimization. Yet I rarely see it mentioned - seems always to come down to binary search ...<p>[1] <a href="http://www.amazon.com/Linear-Nonlinear-Programming-David-Luenberger/dp/0201157942" rel="nofollow">http://www.amazon.com/Linear-Nonlinear-Programming-David-Lue...</a>
This is interesting, a somewhat related post can be found here:<p><a href="http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html" rel="nofollow">http://googleresearch.blogspot.com/2006/06/extra-extra-read-...</a><p>The gist of this is that version of BSearch implemented in the JDK contained a bug due to an overflow error. I recall reading about it some time ago, funny to see it come up again.
Here's a link to some of his work. A big fat hairy perl file:<p><a href="http://cpansearch.perl.org/src/MIRK/Net-Z3950-Simple2ZOOM-1.04/lib/Net/Z3950/Simple2ZOOM.pm" rel="nofollow">http://cpansearch.perl.org/src/MIRK/Net-Z3950-Simple2ZOOM-1....</a><p>Knowing how to write code that is easy to read is just as important, if not more so, than knowing how to write binary searches.
Maybe I was fortunate; I learned how to write a binary search in my lower-level CS courses. I didn't even find it particularly difficult, but then again, the concept was explained quite clearly before I had to code it.
Some people here think this is about coding without testing. No, it's an example of thinking through <i>before</i> testing, about the kind of thinking that's separate from testing. It's not meant as an example of what all programming is about, but a probe of an aspect of programming. So why.<p>Is it okay to write down a guess, then look at it with edge cases in mind, fix and iterate? I think sketching is okay for this exercise as long as you follow through and finish.<p>The difference is that sketching doesn't tell you what the bugs are. Whereas testing can tell you specifically. One's an aid to thought and the other's... an alternative, to be neutral about it.<p>A couple people have described case analysis like simulating tests in your head. I hope they actually use more principled thinking than they're letting on.<p>Iterative coding breaks into two cases: either the task is subjective/aesthetic, like an interaction or layout problem, or it really is an exact task but you don't have it clear in your mind. Everybody recognizes the value of iterating on a fuzzy problem, put that aside. The question is, if it's an exact problem but you don't understand it well, then will test-writing clarify or obscure things?<p>Sometimes I iteratively write and run or test a program until I get to a point where I say, "Okay, <i>now</i> do I understand what this is about? Can I explain it thoroughly in full sentences?" Even so I'm sure I've fooled myself with tests.<p>In real world coding, you aren't given small problems. That doesn't mean small problems are poor examples. Obviously we should break big problems into as small and comprehensible problems as possible. Testing doesn't do that (although it could make incentives).<p>Not to mention the fact that there's no such thing as a complete test for a program with an infinite set of possible inputs. You can test for what seem to be the kinds of bugs the program could have.<p>The unstated assumption of many here is that somehow in the process of testing we'll come upon all the right tests for that program, without any sneaky missed cases. Then you will look at the tests and code and somehow extrapolate or judge that you've covered all the bases. But how sure is this if you still aren't sure exactly what the problem is, or if you don't think about bugs and cases very well?<p>There's a kind of thinking you have to do within and around testing anyway. The write- before- testing challenge tests how well you do that necessary thinking, and how reliably you judge how well you've done. It's an artificial light on a real issue.<p>Btw, my test file, meant to be easily processed in any language: <a href="http://www.mac-guyver.com/switham/2010/04/Binary_Search" rel="nofollow">http://www.mac-guyver.com/switham/2010/04/Binary_Search</a>