On Jan 17, 2012, at 06:16, Rob van der Heij wrote:
>
> (N-1) * cost(P) + log(N) * cost(C) rather than (N/2) * (
> cost(C) + cost(P) )
>
> with cost(C) and cost(P) the cost for key comparison and following a
> pointer respectively. Really depends on the ratio between those two.
> Interesting...
>
For large lists, the dominant terms are
N * cost(P) : N/2 * ( cost(C) + cost(P) )
so the binary search is preferable as long as cost(C) exceeds
cost(P). (Assuming that the test for midpoint doesn't add to
the cost of the binary search.)
Might this be optimized by leaving some breadcrumbs along
the scan for midpoint? Or would the test to determine where
to leave a breadcrumb negate any gain?
In some contexts, z/OS name/token services might be the best
choice -- they've likely done all the optimizing for you.
-- gil
