# search

Category: algorithms | Component type: function

### Prototype

`Search` is an overloaded name; there are actually two `search` functions.

    template <class ForwardIterator1, class ForwardIterator2>
    ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
                            ForwardIterator2 first2, ForwardIterator2 last2);

    template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
    ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
                            ForwardIterator2 first2, ForwardIterator2 last2,
                            BinaryPredicate binary_pred);

### Description

`Search` finds a subsequence within the range `[first1, last1)` that is identical to `[first2, last2)` when compared element-by-element. It returns an iterator pointing to the beginning of that subsequence, or else `last1` if no such subsequence exists. The two versions of `search` differ in how they determine whether two elements are the same: the first uses `operator==`, and the second uses the user-supplied function object `binary_pred`.

The first version of `search` returns the first iterator `i` in the range `[first1, last1 - (last2 - first2))` [1] such that, for every iterator `j` in the range `[first2, last2)`, `*(i + (j - first2)) == *j`. The second version returns the first iterator `i` in `[first1, last1 - (last2 - first2))` such that, for every iterator `j` in `[first2, last2)`, `binary_pred(*(i + (j - first2)), *j)` is `true`. These conditions simply mean that every element in the subrange beginning with `i` must be the same as the corresponding element in `[first2, last2)`.

### Definition

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

### Requirements on types

For the first version:

- `ForwardIterator1` is a model of Forward Iterator.
- `ForwardIterator2` is a model of Forward Iterator.
- `ForwardIterator1`'s value type is a model of EqualityComparable.
- `ForwardIterator2`'s value type is a model of EqualityComparable.
- Objects of `ForwardIterator1`'s value type can be compared for equality with Objects of `ForwardIterator2`'s value type.

For the second version:

- `ForwardIterator1` is a model of Forward Iterator.
- `ForwardIterator2` is a model of Forward Iterator.
- `BinaryPredicate` is a model of Binary Predicate.
- `ForwardIterator1`'s value type is convertible to `BinaryPredicate`'s first argument type.
- `ForwardIterator2`'s value type is convertible to `BinaryPredicate`'s second argument type.

### Preconditions

- `[first1, last1)` is a valid range.
- `[first2, last2)` is a valid range.

### Complexity

Worst case behavior is quadratic: at most `(last1 - first1) * (last2 - first2)` comparisons. This worst case, however, is rare. Average complexity is linear.

### Example

      const char S1[] = "Hello, world!";
      const char S2[] = "world";
      const int N1 = sizeof(S1) - 1;
      const int N2 = sizeof(S2) - 1;

      const char* p = search(S1, S1 + N1, S2, S2 + N2);
      printf("Found subsequence \"%s\" at character %d of sequence \"%s\".\n",
             S2, p - S1, S1);

### Notes

[1] The reason that this range is `[first1, last1 - (last2 - first2))`, instead of simply `[first1, last1)`, is that we are looking for a subsequence that is equal to the complete sequence `[first2, last2)`. An iterator `i` can't be the beginning of such a subsequence unless `last1 - i` is greater than or equal to `last2 - first2`. Note the implication of this: you may call `search` with arguments such that `last1 - first1` is less than `last2 - first2`, but such a search will always fail.

### See also

`find`, `find_if`, `find_end`, `search_n`, `mismatch`, `equal`

Copyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation