Summary

Searching: the process of trying to locate a particular element, called the key, within a collection of elements. A search tells us whether the key is present in the collection, and if it is, at what position it can be found.

Linear Search: checks every element of a list one at a time, without skipping any of them. It works well for small, unsorted lists, but becomes slow and time-consuming as the list grows larger — the time taken increases with the size of the list.

Binary Search: works only on a sorted/ordered list, which it repeatedly divides in the middle. It compares the middle element with the key: if they match, the search succeeds and stops; if the middle element is greater than the key, the search continues only in the first half of the list; if it is smaller, the search continues only in the second half. This splitting and shrinking of the list continues until the key is found or only one element remains.

Why a "Failed" Comparison Still Helps: in binary search, even a comparison that does not find the key is useful — it reveals whether the key lies before or after the current middle position, letting the search narrow down the remaining area at every step.

Hash-Based Searching: needs only a single key comparison to discover whether a key is present, provided every element sits at the position its hash function assigns it. The position is worked out directly from the key using a formula called the hash function.

Collision: what happens when two different elements map to the same slot in the hash table. …