Eventually one will either find an element that has the desired property or reach the end of the structure without finding such an element, thus conclusively proving that there is no such element. Exercise 1 Define a Scheme procedure that searches a list for an element that meets a specified test, returning that element if it is successful and returning the symbol 'nonesuch if it is unsuccessful. Exercise 2 Define a Scheme procedure that reads in Scheme values from a given input port, applying a specified test to each one. The linear search algorithms just described can be quite slow if the data structure to be searched is large. The reason is that one can then use the much faster binary search algorithm.
Binary search is a more specialized algorithm than linear search.
It requires a random-access structure, as opposed to one that offers only sequential access, and it is limited to the kind of test in which one is looking for a particular value that has a unique relative position in some ordering. The idea in a binary search is to divide the sorted vector into two approximately equal parts, examining the element at the point of division to determine which of the parts must contain the value sought. The element at the point of division cannot precede the value sought in the ordering that was used to sort the vector. The search procedure invokes itself recursively to search just the left half of the vector. The value sought cannot precede the element at the point of division.