Very interesting gem on binary seaches.
(via Bill de hÓra).
This entry was posted on Tuesday, June 6th, 2006 at 5:32 pm and is filed under Programming.
You can follow any comments to this entry through the RSS 2.0 feed.
Both comments and pings are currently closed.
Comments are closed.
I would say this is a limitation, not a Bug.
The C/C++ replacement line
> mid = ((unsigned) (low + high)) >> 1;
is not able fix this bug, the limitation (number of elements in the binary tree) is just doubled, not sufficient if array index is an unsigned int.
> mid = ((size_t) low + (size_t) high) >> 1;
would be needed then here.
Even more interesting:
Bserach only works with unique key values, else its not garantueed to return the first entry of the search value (qsort has no prob with multiple keys)
Matthias, of course, it’s not a bug in the binary search algorithm, it’s a limitation of the runtime environment the binary search algorithm is running in.