News for hackers. Stuff that matters.
Re:Are you one of the 10% of programmers who can write a bin... by Dove on Monday April 19, 2010 @05:48PM (#1277945)
Having to do it in C is even more perverse than doing it in my head.

;)

Re:Are you one of the 10% of programmers who can write a bin... by Dove on Monday April 19, 2010 @06:56PM (#1278104)
In all seriousness, if you have to translate it, don't bother. I write in C nearly daily, and I certainly wouldn't trust myself not to lose something in translation.

I'd be interested in what's in your test suite, though. I must sheepishly admit that my 'fairly exhaustive' test consisted of running the above random input until I'd seen all the usual tricky cases go by:

  - an array of length zero
  - an array of length one
  - an array of length two
  - the value is present
  - the value is absent and too small
  - the value is absent and too large
  - the value is absent and in the middle
  - the value is the first entry
  - the value is the last entry
  - the array is all one value 
  - there are multiple copies of the value you're looking for
If you've got anything more interesting in that test suite, that'd be good to know. Like I said, I represent the one-bazillionth of programmers that actually have a recurring professional interest in correctly coding binary searches.
Re:Are you one of the 10% of programmers who can write a bin... by ay on Monday April 19, 2010 @11:38PM (#1278559)
"the array is all one value" got me. After fixing that, despite of the excessive verbosity, my experiment in literate programming passes the other tests - but I'm sure I coded a few more bugs in it - if you have some stock suite to get it through - would be very interested to know how many!

http://stdio.be/mybsearch/mybsearch.txt for the text and the http://stdio.be/mybsearch/mybsearch.c for the notangle-d C code, if you fancy to look at it.

Re:Are you one of the 10% of programmers who can write a bin... by joezydeco on Monday April 19, 2010 @09:36PM (#1278354)
An array of length Maxint?
Re:Are you one of the 10% of programmers who can write a bin... by ableal on Tuesday April 20, 2010 @06:07AM (#1279054)
Good call. As per link in http://news.ycombinator.com/item?id=1277701 (elsewhere in this page):

the binary search program that Bentley proved correct and subsequently tested in Chapter 5 of Programming Pearls contains a bug [...] it fails if the sum of low and high is greater than the maximum positive int