"Searching is a very basic operation. Given a collection of data, we wish to find a particular element or elements that match a certain criteria. More formally, we have the following. Problem 1 (Searching). Given: a collection of elements, A = { a₁, a₂, . . . , aₙ } and a key element eₖ. Output: The element aᵢ in A such that aᵢ = eₖ. The “equality” in this problem statement is not explicitly specified. In fact, this is a very general, abstract statement of the basic search problem. We didn’t specify that the “collection” was an array, a list, a set, or any other particular data structure. Nor did we specify what type of elements were in the collection. They could be numbers, they could be strings, they could be objects. There are many variations of this general search problem that we could consider. For example, we could generalize it to find the “first” or “last” such element if our collection is ordered. We could find all elements that match our criteria. Some basic operations that we’ve already considered such as finding the minimum or maximum (extremal elements), or median element are also variations on this search problem. When designing a solution to any of these variations additional considerations must be made. We may wish our search to be index-based (that is, output the index i rather than the element aᵢ). We may need to think about how to handle unsuccessful searches (return null? A special flag value? Throw an exception?, etc.)."