Sorted Order

• If we keep the file in sorted order, searching is faster

• We can use a binary search

  • This is the method we use for searching the telephone book

• Idea:

  • Look at a record near the middle of the file

    • If the record is too early, look only at the last half of the file

    • If the record is too late, look only at the first half of the file

  • Repeat on successively smaller segments of the file

  • The standard Search::Dict module does this

Next

Copyright © 2003 M. J. Dominus