
Computer Science
Figure 6.4 The action of a binary search (binary chop) to find an item in a list
that has been placed into order
comparisons that must be made in a binary search is at most only ten for a list
of 1024 items, as distinct from an average of 512 for a one-by-one
comparison, and in general the maximum number of comparisons n is such
that 2
n
is equal to or just greater than the number of key items (so that the
number of key items is less than 2
n+1
). Once the key has been located from
the index file, the sector number can be obtained and the record copied from
the main file. This form of keying, however, is more often applied to ...