Program gives the naıve version
of the `Find` member function of the `MWayTree` class.
The `Find` member function takes
a `const` reference to an `Object` instance
and locates the item in the search tree which matches the given instance.

**Program:** `MWayTree` Class `Find` Member Function Definition(Linear Search)

Consider the execution of the `Find` function for a node *T*
of a an *M*-way search tree.
Suppose the object of the search is *x*.
Clearly, the search fails when (lines 3-4).
In this case, a reference to the `NullObject` instance is returned.
Suppose .
The linear search on lines 5-14 considers the keys
, , , ..., , in that order.
If a match is found,
a reference to the matching object is returned immediately (lines 9-10).

Otherwise, when the main loop terminates there are three possibilities:
*i*=0 and ;
and ; or
*i*=*n*-1 and .
In all three cases,
the appropriate subtree in which to continue search is (line 15).

Clearly the running time of Program
is determined by the main loop.
In the worst case, the loop is executed *M*-1 times.
Therefore, at each node in the search path
at most *M*-1 object comparisons are done.

Consider an unsuccessful search in an *M*-way search tree.
The running time of the `Find` function is

in the worst case,
where *h* is the height of the tree
and is the time required to compare two objects.
Clearly, the time for a successful search has the same asymptotic bound.
If the tree is balanced and ,
then the running time of Program
is ,
where *K* is the number of keys in the tree.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.