4 ms·

Having to do it in C is even more perverse than doing it in my head. ;)

by Dove 17y ago

Dove 17y ago
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.
- joezydeco 17y ago
  An array of length Maxint?
  - ableal 17y ago
    Good call. As per link in http://news.ycombinator.com/item?id=1277701 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
- ay 17y ago
  "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 http://stdio.be/mybsearch/mybsearch.txt for the text and the http://stdio.be/mybsearch/mybsearch.c http://stdio.be/mybsearch/mybsearch.c for the notangle-d C code, if you fancy to look at it.

Having to do it in C is even more perverse than doing it in my head. ;)

by Dove 17y ago

Having to do it in C is even more perverse than doing it in my head. ;)

Dove 17y ago

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.

joezydeco 17y ago
An array of length Maxint?
- ableal 17y ago
  Good call. As per link in http://news.ycombinator.com/item?id=1277701 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
ay 17y ago
"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 http://stdio.be/mybsearch/mybsearch.txt for the text and the http://stdio.be/mybsearch/mybsearch.c http://stdio.be/mybsearch/mybsearch.c for the notangle-d C code, if you fancy to look at it.