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.
The listsearch
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) (listsearch ef (cdr p)))))
For example,
Assuming the matching function has constant running time, the worst case running time of listsearch
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 listsearch
, 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
false
as an element, we do not know when thelistsearch
result isfalse
if it means the element is not in the list or the element whose value isfalse
satisfies the property. An alternative would be to produce an error if no satisfying element is found, but this is more awkward whenlistsearch
is used by other procedures. ↩