Searching

Scan elements one by one until the target is found or the input is exhausted.

Find a target in a sorted array by repeatedly halving the search range.

Find the extremum of a unimodal function by discarding one third of the range per step.

Search a sorted array by jumping ahead in fixed blocks of size √n, then scanning linearly within the block.

Double an index until the target is bracketed, then binary search inside that bracket.

Find the k-th smallest element in expected O(n) by partitioning like quicksort but recursing into only one side.