casa  $Rev:20696$
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Public Member Functions
casa::BinarySearch_global_functions_binarysearch Struct Reference

Binary search a sorted, linear, data structure. More...

#include <BinarySearch.h>

List of all members.

Public Member Functions

template<class Container , class ElType >
Int binarySearch (Bool &found, const Container &container, const ElType &value, uInt n, Int lower=0)
 Search container for value.
template<class Container , class ElType >
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.

Detailed Description

Binary search a sorted, linear, data structure.

Review Status

Reviewed By:
Ger van Diepen
Date Reviewed:
1995/03/31
Test programs:
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.
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;

Warning: 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)

Template Type Argument Requirements (ElType)

To Do

Definition at line 135 of file BinarySearch.h.


Member Function Documentation

template<class Container , class ElType >
Int casa::BinarySearch_global_functions_binarysearch::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.

template<class Container , class ElType >
Int casa::BinarySearch_global_functions_binarysearch::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.


The documentation for this struct was generated from the following file: