AlgorithmsAlgorithmsCollege

Searching and Sorting

Linear and binary search; selection, insertion and merge sort.

Searching finds an item in a collection. Linear search checks each element in turn and works on any list in $O(n)$ time. Binary search works only on sorted data: it checks the middle element and discards half the list each step, finding any item among a million in about 20 comparisons.

Sorting puts data in order so that binary search and many other algorithms become possible. Simple sorts such as selection and insertion sort take $O(n^2)$ time; efficient sorts such as merge sort and quicksort take $O(n \log n)$ on average, which is the best possible for comparison-based sorting.

Key ideas

Binary search needs a sorted list and takes at most $\lceil \log_2(n + 1) \rceil$ comparisons.
Insertion sort is fast on nearly sorted data.
Merge sort is always $O(n \log n)$ but uses extra memory.
A stable sort keeps equal items in their original order.

Worked example

Binary search for 23 in `[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]`.

Low 0, high 9: middle index 4 holds 16; $23 > 16$ , so search indices 5-9.
Middle index 7 holds 56; $23 < 56$ , so search indices 5-6.
Middle index 5 holds 23. Found in 3 comparisons.

Answer: Index 5, after 3 comparisons

Common mistakes

Running binary search on unsorted data.
Off-by-one errors when updating low and high.
Assuming quicksort is always $O(n \log n)$ ; its worst case is $O(n^2)$ .

Practice questions

Try each one, then open the answer. Numerical answers on this page are verified by an automated calculation check.

1.Worst-case comparisons for binary search on 1000 sorted items.
Show answer
$10$
2.Worst-case comparisons for linear search on 1000 items.
Show answer
$1000$
3.Comparisons selection sort makes on 6 items: $\frac{n(n - 1)}{2}$ .
Show answer
$15$

Key ideas

Worked example

Common mistakes

Practice questions

More in Algorithms