Very interesting gem on binary seaches.
(via Bill de hÓra).
« Automating "All" Tests | Main | World Cup Envy »
Very interesting gem on binary seaches.
(via Bill de hÓra).
This page contains a single entry from the blog posted on June 6, 2006 5:32 PM.
The previous post in this blog was Automating "All" Tests.
The next post in this blog is World Cup Envy.
Many more can be found on the main index page or by looking through the archives.
Comments (2)
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.
A
> 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)
Posted by M.Schwarz | June 8, 2006 3:07 PM
Posted on June 8, 2006 15:07
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.
Posted by Hans Martin Kern | June 8, 2006 6:40 PM
Posted on June 8, 2006 18:40