.\" ident	@(#)Array_alg:man/search.3	3.2
.\"
.\" C++ Standard Components, Release 3.0.
.\"
.\" Copyright (c) 1991, 1992 AT&T and UNIX System Laboratories, Inc.
.\" Copyright (c) 1988, 1989, 1990 AT&T.  All Rights Reserved.
.\"
.\" THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T and UNIX System
.\" Laboratories, Inc.  The copyright notice above does not evidence
.\" any actual or intended publication of such source code.
.\" 
.TH \f3search\fP \f3Array_alg(3C++)\fP " "
.SH NAME
search \- find a matching subarray in an array
.SH SYNOPSIS OF Array_alg.h
.Bf

    template <class \*(gt>
    const \*(gt* search(
	const \*(gt* b1,
	const \*(gt* e1,
	const \*(gt* b2,
	const \*(gt* e2
    );
    template <class \*(gt>
    const \*(gt* search_r(
        int (*rel)(const \*(gt*,const \*(gt*),
	const \*(gt* b1,
	const \*(gt* e1,
	const \*(gt* b2,
	const \*(gt* e2
    );
.Be
.SH ASSUMPTIONS
.PP
(1) For the plain version, \*(gt\f4::operator==\f1
defines an equivalence relation on \*(gt
.br
(2) For the relational version, \f4rel\f1 
defines an equivalence relation on \*(gt
.SH DESCRIPTION
.PP
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 \f20\f1.
.sp 0.5v
.IP "\f4template <class \*(gt>\f1"
.IC "\f4const \*(gt* search(\f1"
.IC "\f4    const \*(gt* b1,\f1"
.IC "\f4    const \*(gt* e1,\f1"
.IC "\f4    const \*(gt* b2,\f1"
.IC "\f4    const \*(gt* e2\f1"
.IC "\f4);\f1"
Uses \f4\*(gt::operator==\f1 to define equality.
.IP "\f4template <class \*(gt>\f1"
.IC "\f4const \*(gt* search_r(\f1"
.IC "\f4    int (*rel)(const \*(gt*,const \*(gt*),\f1"
.IC "\f4    const \*(gt* b1,\f1"
.IC "\f4    const \*(gt* e1,\f1"
.IC "\f4    const \*(gt* b2,\f1"
.IC "\f4    const \*(gt* e2\f1"
.IC "\f4);\f1"
Uses \f4rel\f1 to define equality.  
That is, if \f4p\f1 and \f4q\f1 are pointers 
into the first and second array, respectively, 
then \f4p\f1 and \f4q\f1 begin matching subarray 
of length 1 if \f4rel(p,q)==0\f1
.SH COMPLEXITY
.PP
If \f2N\f1 and \f2M\f1 are 
the sizes of first and second arrays, 
respectively,
then complexity is \f2O(N*M)\f1.
At most \f2N*M\f1 equality tests are done. 
However, it is quite fast on the
average in most practical cases.
.SH NOTES
Because a Block (see \f3Block(3C++)\f1)
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.
.SH SEE ALSO
.Bf
\f3intro(.)\f1
\f3Block(3C++)\f1
.Be