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 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

(define (list-search ef p)
  (if (null? p) false ; Not found
      (if (ef (car p)) (car p) (list-search ef (cdr p)))))

For example,

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.

  1. If the input list contains false as an element, we do not know when the list-search result is false if it means the element is not in the list or the element whose value is false satisfies the property. An alternative would be to produce an error if no satisfying element is found, but this is more awkward when list-search is used by other procedures.