Searching and Hashing

It is important to understand what search is and when it is appropriate. This page explains sequential and binary search, and their implementation. There is also the matter of hashing as a storage and search technique. In so doing, we introduce the unordered map and how to implement a map abstract data type using hashing. Read Sections 6.1-6.5. You may also find Sections 6.6-6.11 useful for practice.

6. Summary

A sequential search is $O (n)$

for ordered and unordered lists.
A binary search of an ordered list is $O (\log n)$
in the worst case.
Hash tables can provide constant time searching.