Searching and Sorting

Finding and Ordering Data

Searching (finding an item) and sorting (putting items in order) are the most fundamental algorithmic tasks, and they beautifully illustrate the complexity ideas of the previous lesson.

Searching:

• Linear search scans the list from the start, checking each element — $O(n)$. It works on any list, sorted or not.
• Binary search repeatedly halves a sorted list: compare the target to the middle element, then discard the half that cannot contain it — $O(\log n)$, dramatically faster. Its precondition is essential: binary search requires the data to be sorted. On an unsorted list it gives wrong answers.

This reveals a classic trade-off: sorting a list first (once) lets you binary-search it many times cheaply — worthwhile when you search repeatedly.

Sorting arranges elements in order. Simple methods like bubble sort, selection sort, and insertion sort are intuitive but run in $O(n^2)$ — fine for small data, slow for large. Efficient methods — merge sort and quicksort — run in $O(n \log n)$, the best achievable for comparison-based sorting, using divide and conquer: split the data, sort the pieces (recursively), and combine. The gap between $O(n^2)$ and $O(n \log n)$ is the difference between a slow and a usable sort at scale.

Sorting is a workhorse subroutine: once data is sorted, searching, finding duplicates, computing medians, and merging datasets all become easier. Choosing between algorithms is a matter of the data size, whether it is already partly ordered, and how the operation will be repeated — the everyday application of complexity analysis.

Common pitfall: applying binary search to an unsorted list. Binary search's speed comes entirely from the data being sorted — it discards half the list assuming order, so on unsorted data it will skip past the target and report it missing (or find the wrong thing). If the list is not sorted, either sort it first (then binary-search) or use linear search, which needs no ordering.