BinarySearch.h

Classes

Global Functions -- Binary search a sorted, linear, data structure. (full description)

Binary search a sorted, linear, data structure. (source)

Interface

Int binarySearch(Bool &found, const Container &container, const ElType &value, uInt n, Int lower=0)

Int binarySearchBrackets(Bool &found, const Container &container, const ElType &value, uInt n, Int lower=0)

Description

Review Status

Reviewed By:

Ger van Diepen

Date Reviewed:

1995/03/31

Programs:

Tests:

tBinarySearch

Synopsis

These binary search functions work on sorted, 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 container must be sorted (sorting is available through the Sort and GenSort classes, and from various Table sort functions). The returned index is in the range [0..n] inclusive. That is, from the first element of the container to one past the last element of the container (zero-based indices). If the container is sorted in ascending order, the returned index is the first one whose element is greater than or equal to the searched for value. If it is sorted in descending order, the returned index is the first which is less than or equal to the searched for value. That is, the returned index gives the position at which the value would be inserted (possibly either at the end, or requiring the existing values to be "pushed" to the right) maintaining the sort order. Obviously index n can only be returned if the value searched for is past the end of the array, thus has to be inserted at the end.

The functions determine for themselves whether the container is sorted in ascending or descending order by comparing the first and last element.

While normally you want to search a container with indices in the range [0 ... n-1], any desired lower bound may be used instead.

The functions do not check if the container is valid, i.e. if the container is sorted and if the container does not contain duplicate values.

These functions loosely follow some written by Ger van Diepen in a more specialized context.

Example

    Vector<Int> vi;
    ...  // Sets vi somehow
    genSort(vi);
    Int val;
    Bool found;
    while (cin >> val && val != -999) {
        Int where = binarySearch(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

I found that I (BEG) was writing binary search functions several times, for example when checking whether the cached off and gain scans in time sorted data needed to be refilled. It generally seems like a useful little utility function.

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.

Template Type Argument Requirements (ElType)

The less than operator (<) and greater than (>) operators need to be defined, and have their usual ordering relations.

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 binarySearch(Bool &found, const Container &container, const ElType &value, uInt n, Int 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.

This version of the function is for containers that use () for indexing.

Int binarySearchBrackets(Bool &found, const Container &container, const ElType &value, uInt n, Int lower=0)

This version of the function is for containers that use [] for indexing.