Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://www.atnf.csiro.au/computing/software/casacore/casacore-1.2.0/doc/html/structcasa_1_1BinarySearch__global__functions__binarysearch.html
Дата изменения: Unknown Дата индексирования: Tue Feb 15 00:40:50 2011 Кодировка: Поисковые слова: aurora |
Binary search a sorted, linear, data structure. More...
#include <BinarySearch.h>
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. |
Binary search a sorted, linear, data structure.
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.
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; } }
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.
Definition at line 135 of file BinarySearch.h.
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.
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.