Searching
Searching is one of the core operations in data structures: it answers whether a given value exists in a collection of data, and if so, where. Database lookups, symbol resolution in a compiler, and finding an item in a cache all reduce to this question, and the cost of the answer is what decides whether a program feels instant or sluggish. The chapter starts from the simplest strategies, where a target is compared against every element in turn, and moves to the structures that let you skip most of the work: ordered tables that halve the search space, hash tables that jump straight to a bucket, and B-trees that keep large indexes shallow so that each step touches one disk page. By the end you will be able to state the idea behind sequential, binary and block search and their complexity, explain how a B-tree and a B+ tree are shaped and how a lookup travels through them, build a hash table and reason about its collision handling and load factor, implement naive and KMP string matching, and pick a search strategy that suits the data you actually have.
