Solution
= 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.