Three Algorithms Every Paper Asks For

Arrays store data; algorithms answer questions about it. Three of them, linear search, binary search, and bubble sort, appear on essentially every C exam, and they are worth knowing far beyond the exam: they are the simplest members of the search and sort families that computing runs on, and tracing them by hand is how algorithmic thinking starts.

Linear Search: Look at Everything

The obvious way to find a value: walk the array until you meet it or run out.

Try 55, then 10, then 99. The pattern to internalize: a result variable starts at an impossible value (-1 can never be an index), the loop breaks on success, and the answer is read afterwards. Duplicates go to the earliest match because the walk is left to right. Cost: up to n comparisons, every element in the worst case.

Binary Search: Halve the Problem

If the array is sorted, you can do enormously better. Compare the target with the middle element: too small means the answer lives in the left half, too big means the right, equal means done. Each comparison discards half the remaining candidates.

The window [lo, hi] shrinks by half per pass, so seven elements need at most three comparisons, and a million need only twenty: the doubling-halving arithmetic from the bitwise lesson, working for you. The two preconditions exams probe: the array must be sorted, binary search on unsorted data returns confident nonsense, and the window update must skip mid itself (mid + 1, mid - 1), or a missing target loops forever.

Bubble Sort: Neighbors Swap Until Ordered

Sorting is how data earns binary search. Bubble sort is the teaching sort: sweep the array comparing neighbors, swapping any pair out of order; each sweep floats the largest remaining value to its final place at the end, so the next sweep can stop one element earlier.

Every piece is examinable. The swap needs a temporary: temp holds one value while the other moves, the three-assignment dance that C offers no shortcut for. The inner bound COUNT - 1 - i skips the already-settled tail, and its - 1 also keeps values[j + 1] in bounds, an off-by-one with teeth. The nested shape means roughly n squared comparisons, last chapter's multiplication observation made concrete: fine for a classroom's worth of data, unusable for a million, which is why the library sorts you will meet later exist.

Tracing one full outer pass on paper, writing the array after each swap, is the exam skill; do it once with the five values above and the algorithm is yours.

Key Takeaways

  • Linear search: walk with a result index started at -1, break on match; up to n comparisons, works on any array.
  • Binary search: sorted input only; halve the [lo, hi] window with mid + 1/mid - 1 updates; about log n comparisons, and forgetting either precondition is the classic failure.
  • Bubble sort: neighbor compare-and-swap sweeps, largest value settling last each pass; inner bound COUNT - 1 - i handles both the settled tail and the j + 1 bounds.
  • Swapping two values takes a temporary and three assignments.
  • Costs matter: n for linear, log n for binary, n squared for bubble, the first vocabulary of algorithm analysis.