Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 2 / a / Solution

Linear search examines successive entries until a match or a stopping condition is reached; in the worst case it inspects $n$ entries. Binary search uses a sorted array to discard about half of the remaining candidates after each comparison, requiring $O(\log (n+1))$ comparisons. Its logarithmic guarantee also requires constant-cost indexed access, as supplied by an array; the same index operations on a linked list would not be constant-cost.