LinearSearch.h

Classes

Global Functions -- Linear search a linear data structure. (full description)

Linear search a linear data structure. (source)

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)

Description

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.

Tip While normally you want to search a container with indices in the range [0 ... n-1], any desired lower bound may be used instead.
Caution 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)

Template Type Argument Requirements (ElType)

To Do

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.