LinearSearch.h
Classes
- Global Functions -- Linear search a linear data structure. (full description)
Interface
- Int linearSearch1 (const Container& container, const ElType& value, uInt lower = 0)
- Int linearSearch (Bool& found, const Container& container, const ElType& value, uInt n, uInt lower=0)
- Int linearSearchBrackets1 (const Container& container, const ElType& value, uInt lower = 0)
- Int linearSearchBrackets (Bool& found, const Container& container, const ElType& value, uInt n, uInt lower=0)
Review Status
- Reviewed By:
- UNKNOWN
- Date Reviewed:
- before2004/08/25
- Programs:
- Tests:
Synopsis
These linear search functions work on linear data structures
which have operator() or operator[] defined on them (e.g.
C-array, Vector, IPosition, Block, ScalarColumn, etc.)
Two versions of the functions are provided, one which uses
parentheses () for indexing, one which uses square brackets [] (obviously
the latter one can also be used for ordinary C-style pointers and arrays).
It is assumed that the container uses zero-based indexing.
The returned index is in the range [0..n-1]. When the value is
not found, -1 is returned.
While normally you want to search a container with indices in the range
[0 ... n-1], any desired lower bound may be used instead.
Linear searching should only be used for small arrays.
For larger arrays sort and
binarySearch
should be used.
Example
Vector<Int> vi;
... // Sets vi somehow
Int val;
Bool found;
while (cin >> val && val != -999) {
Int where = linearSearch(found, vi, val, vi.nelements());
if (found) {
cout << "Found " << val << " at position " << where << endl;
} else {
cout << val << " is not in the vector, but it belongs at " <<
where << endl;
}
}
Motivation
Neil Killeen needed a linear search on a Vector.
Modelling it after BinarySearch was the logical step to take.
Template Type Argument Requirements (Container)
- operator(Int) or operator[Int] needs to be defined.
- The index must be zero based.
- The result of that indexing must be an expression that can be
compared with an object of class ElType. Normally in fact it would
be a temporary of class ElType.
- Member function nelements() is needed when the shorthand is taken.
Template Type Argument Requirements (ElType)
- The equal operator (==) need to be defined.
To Do
- I suspect that an implementation is possible that only calls
operator() or [] once during each evaluation of the while loop.
- MACROize implementation so that code isn't repeated twice. Or,
possibly implement one using the other (e.g. by introducing an adapter
class that turns (i) into [i].
Member Description
Int linearSearch1 (const Container& container, const ElType& value, uInt lower = 0)
Search container for value. There are assumed to be at least
n elements in the container. The container will be searched for
indices in the range [lower ... lower + n - 1] Return the index
of the first element which is greater than or equal to (ascending order) or
less than or equal to (descending order) the value.
When not found, -1 is returned and found is set to False.
This version of the function is for containers that use () for indexing.
Int linearSearchBrackets1 (const Container& container, const ElType& value, uInt lower = 0)
Search container for value. There are assumed to be at least
n elements in the container. The container will be searched for
indices in the range [lower ... lower + n - 1] Return the index
of the first element which is greater than or equal to (ascending order) or
less than or equal to (descending order) the value.
When not found, -1 is returned and found is set to False.
This version of the function is for containers that use [] for indexing.
Int linearSearch (Bool& found, const Container& container, const ElType& value, uInt n, uInt lower=0)
Int linearSearchBrackets (Bool& found, const Container& container, const ElType& value, uInt n, uInt lower=0)
Search container for value. There are assumed to be at least
n elements in the container. The container will be searched for
indices in the range [lower ... lower + n - 1] Return the index
of the first element which is greater than or equal to (ascending order) or
less than or equal to (descending order) the value.
When not found, -1 is returned and found is set to False.