Skip to content
Topos Uranos
English

Searching and sorting

Summary

Searching and sorting are the two fundamental problems on collections, and there is a trade-off between them: sorting once has a cost, but it makes every later search cheaper. The lesson writes linear and binary search by hand, the latter discarding half of the data at each step when the data are sorted; it justifies binary search with its invariant, proves that it terminates, counts its iterations and studies the three errors that ruin it. Next come selection sort and insertion sort, with their invariants and the exact count of their comparisons; then the same problems with the ranges library, and the count that decides when it pays to sort before searching.

Learning objectives

  1. Implement linear search and binary search, and justify binary search with its invariant (“if the value is present, it lies between low and high”), together with the proof that it terminates.
  2. Implement selection sort and insertion sort, state the invariant of each one and count their comparisons in the best and in the worst case.
  3. Use std::ranges::sort, std::ranges::contains, std::ranges::find, std::ranges::binary_search and std::ranges::lower_bound instead of hand-written versions when appropriate, respecting their preconditions.
  4. Decide, according to the number of searches expected, whether it pays to sort the data before searching them, and justify the decision with the count of comparisons.

Linear search

To search is to answer, given a collection and a value, whether the value is present and where. Without information about the order of the data, there is no strategy other than looking at them one by one: this is linear search. When the value is absent, this course returns values.size(), the first position that does not belong to the vector: it is not a valid index, so it cannot be mistaken for an answer, and it is the same convention the library follows, as the fifth section will show.

C++ program
#include <cstddef>#include <print>#include <vector>​// Precondition: none.// Postcondition: returns the smallest index i with values[i] == target,// or values.size() if target is absent.std::size_t linearSearch(const std::vector<int>& values, int target){    // Invariant: target is not in values[0], ..., values[i - 1].    for (std::size_t i{0}; i < values.size(); ++i) {        if (values[i] == target) {            return i;        }    }    return values.size();}​int main(){    const std::vector<int> codes{405, 112, 318, 207, 112, 530};    for (const int target : {207, 112, 999}) {        const std::size_t pos{linearSearch(codes, target)};        if (pos == codes.size()) {            std::println("{}: not found", target);        } else {            std::println("{}: position {}", target, pos);        }    }}
Output
207: position 3112: position 1999: not found

The invariant on line 10 gives correctness. At the start, with i equal to 0, it states something about an empty stretch and is true. If it holds at the start of an iteration and values[i] is not the value sought, it holds at the end with one more element. Now, the loop has two exits: if return i; executes, values[i] is the value sought and, by the invariant, no earlier element was, whence i is the first occurrence (that is why 112, which appears twice, is reported at position 1); if the loop ends through its condition, i equals values.size() and the invariant says the value is nowhere. The return inside the loop ends the function, and with it the loop, and saves a flag.

The cost, in the sense of the lesson The cost of an algorithm, is measured by the comparisons values[i] == target. If the value is absent, exactly nn are made, one per element: the worst case. If it is at position pp, p+1p + 1 are made. Linear search is, then, O(n)O(n): with twice the data, twice the work. Without additional information it cannot be done better: an algorithm that skipped looking at an element would not know whether the value was there.