The algorithm compares x to each entry in turn until a match is found or the list is exhausted.
We postpone the proof until Section 2.