ABSTRACT
S EARCHING IS the second fundamental operation we will study in this course.
As with sorting, efficient searching is a critical foundation in computer science.
We review O ( n ) linear search and O
( lg n
) binary search, then discuss more sophis-
ticated approaches. Two of these techniques, trees and hashing, form the basis for
searching very large data collections that must remain on disk.
