8.2.1 Unstructured Search
Finding an item that satisfies an arbitrary property in unstructured data requires testing each element in turn until one that satisfies the property is found. Since we have no more information about the property or data, there is no way to more quickly find a satisfying element.
list-search procedure takes as input a matching function and a list, and outputs the first element in the list that satisfies the matching function or
false if there is no satisfying element:1
(if (null? p) false ; Not found
(if (ef (car p)) (car p) (list-search ef (cdr p)))))
Assuming the matching function has constant running time, the worst case running time of
list-search is linear in the size of the input list. The worst case is when there is no satisfying element in the list. If the input list has length $n$, there are $n$ recursive calls to
list-search, each of which involves only constant time procedures.
Without imposing more structure on the input and comparison function, there is no more efficient search procedure. In the worst case, we always need to test every element in the input list before concluding that there is no element that satisfies the matching function.
If the input list contains
falseas an element, we do not know when the
falseif it means the element is not in the list or the element whose value is
falsesatisfies the property. An alternative would be to produce an error if no satisfying element is found, but this is more awkward when
list-searchis used by other procedures. ↩