DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH PRINT BOOK

# 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++)