I'll do it tomorrow at work, but if someone can post and/or email me an equivalent C version it will reduce my time. Not a problem, but just more convenient.
You'll need to give me some way to contact you so I can send you the results.
EDIT: I've just realised the spec I usually give asks for the first occurence of a key to be returned in the case where there are duplicate keys. I'll modify my tests to account for that. It's an especially useful feature in a binary search, but rarely implemented.
;)
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.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.
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