# search(3C++)

**search --
find a matching subarray in an array
**

## Synopsis

template <class **T**>
const **T*** search(
const **T*** b1,
const **T*** e1,
const **T*** b2,
const **T*** e2
);
template <class **T**>
const **T*** search_r(
int (*rel)(const **T***,const **T***),
const **T*** b1,
const **T*** e1,
const **T*** b2,
const **T*** e2
);

## Assumptions

(1) For the plain version, **T::operator==** defines an equivalence
relation on **T**.

(2) For the relational version, **rel** defines an equivalence
relation on **T**.

## Description

These functions return a location in the first array at which begins a
subarray of the same size as the second array such that every
element in this subarray is
equal to the corresponding element of the second array.
If such a location does
not exist, they return *0*.

template <class T>
const T* search(
const T* b1,
const T* e1,
const T* b2,
const T* e2
);

Uses **T::operator==** to define equality.

template <class T>
const T* search_r(
int (*rel)(const T*,const T*),
const T* b1,
const T* e1,
const T* b2,
const T* e2
);

Uses **rel** to define equality. That is, if
**p** and **q** are pointers into the first and
second array, respectively, then **p** and **q**
begin matching subarray of length 1 if **rel(p,q)==0**.

## Complexity

If *N* and *M* are the
sizes of first and second arrays, respectively, then complexity is
*O(N*M)*. At most *N*M* equality
tests are done.
However, it is quite fast on the average in most practical cases.

## Notes

Because a Block (see **Block(3C++)**) can always be used wherever
an array is called for, Array Algorithms can also be used with Blocks.
In fact,
these two components were actually designed to be used together.

## References

**Array_alg**(3C++),
**Block**(3C++)

*
© 2004 The SCO Group, Inc. All rights reserved.
*

UnixWare 7 Release 7.1.4 - 25 April 2004