PRO binary_search, v1, v2, nmatch, lo_ind, hi_ind, NO_PAR_CHECK = no_par_check
; Description: This module searches for the set of values from a set of input data "v2"
; that have exactly the same value as "v1". The module employs a fast
; binary search algorithm and it is for this reason that the set of data
; values "v2" must already be sorted into ascending order. The indices of
; the matching data values from "v2" are returned as the range of indices
; delimited by "lo_ind" and "hi_ind" respectively.
;
; N.B: (i) If you want to perform multiple binary searches on the same
; data "v2", but with different values of "v1", then it is much
; more efficient to use the DanIDL module "find_elements_in_set.pro"
; because the data "v2" is not copied on each call to the binary
; search algorithm.
;
; (ii) This module works for any number type for the input parameters
; "v1" and "v2", and it also works if "v1" and "v2" are of string
; type.
;
; (iii) I have proved using proof by induction that the algorithm
; implemented in this code will always give the correct answer.
;
; Input Parameters:
;
; v1 - ANY SCALAR - The value for which exactly matching data values in "v2" are to
; be found. This parameter must be defined, and not a structure.
; v2 - ANY SCALAR/VECTOR/ARRAY - The set of data values to be searched for exact
; matches, already sorted into ascending order. This
; parameter must have the same variable type as the
; parameter "v1".
;
; Output Parameters:
;
; nmatch - LONG - The number of values from "v2" that have exactly the same value as
; "v1". If the module fails, then the value of this parameter is set
; to "-1".
; lo_ind - LONG - The lower index of the range of indices for the exactly matching data
; values from "v2". If there are no exactly matching data values, then
; "lo_ind" is returned with a value of "-1".
; hi_ind - LONG - The upper index of the range of indices for the exactly matching data
; values from "v2". If there are no exactly matching data values, then
; "hi_ind" is returned with a value of "-1".
;
; Keywords:
;
; If the keyword NO_PAR_CHECK is set (as "/NO_PAR_CHECK"), then the module will not
; perform parameter checking on the input parameters, reducing module overheads.
;
; Author: Dan Bramich (dan.bramich@hotmail.co.uk)
;
; History:
;
; 19/01/2010 - Module created (dmb).
;Set the default output parameter values
;Perform parameter checking if not instructed otherwise
;Check that "v1" is defined, and that it is not a structure
;Check that "v1" is a scalar
;Check that "v2" has the same variable type as "v1"
;Determine the number of elements in "v2"
;If "v1" does not lie in the range of the data values in "v2", then there are no data
;values in "v2" that have exactly the same value as "v1", and the module will finish
;Use a binary search algorithm to find a subscript of "v2" with a corresponding data
;value that exactly matches the value of "v1", if it exists
;If there are no data values in "v2" that have exactly the same value as "v1", then
;the module will finish
;Determine the lowest subscript in the set of data values "v2" with a corresponding
;data value that exactly matches the value of "v1"
;Determine the highest subscript in the set of data values "v2" with a corresponding
;data value that exactly matches the value of "v1"
;Count the number of matching data values