htswanalysis/MACS/lib/gsl/gsl-1.11/interpolation/bsearch.h

   1 /* interpolation/bsearch.h
   2  *
   3  * Copyright (C) 1996, 1997, 1998, 1999, 2000, 2004 Gerard Jungman
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 3 of the License, or (at
   8  * your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  18  */
  19
  20 /* Author:  G. Jungman
  21  */
  22 #ifndef __GSL_INTERP_BSEARCH_H__
  23 #define __GSL_INTERP_BSEARCH_H__
  24
  25
  26 /* Perform a binary search of an array of values.
  27  *
  28  * The parameters index_lo and index_hi provide an initial bracket,
  29  * and it is assumed that index_lo < index_hi. The resulting index
  30  * is guaranteed to be strictly less than index_hi and greater than
  31  * or equal to index_lo, so that the implicit bracket [index, index+1]
  32  * always corresponds to a region within the implicit value range of
  33  * the value array.
  34  *
  35  * Note that this means the relationship of 'x' to x_array[index]
  36  * and x_array[index+1] depends on the result region, i.e. the
  37  * behaviour at the boundaries may not correspond to what you
  38  * expect. We have the following complete specification of the
  39  * behaviour.
  40  * Suppose the input is x_array[] = { x0, x1, ..., xN }
  41  *    if ( x == x0 )           then  index == 0
  42  *    if ( x > x0 && x <= x1 ) then  index == 0, and sim. for other interior pts
  43  *    if ( x == xN )           then  index == N-1
  44  *    if ( x > xN )            then  index == N-1
  45  *    if ( x < x0 )            then  index == 0
  46  */
  47 size_t
  48 gsl_interp_bsearch(
  49   const double x_array[], double x,
  50   size_t index_lo,
  51   size_t index_hi
  52   );
  53
  54
  55 #ifdef HAVE_INLINE
  56 extern
  57 inline
  58 size_t
  59 gsl_interp_bsearch(
  60   const double x_array[], double x,
  61   size_t index_lo,
  62   size_t index_hi
  63   )
  64 {
  65   size_t ilo = index_lo;
  66   size_t ihi = index_hi;
  67   while(ihi > ilo + 1) {
  68     size_t i = (ihi + ilo)/2;
  69     if(x_array[i] > x)
  70       ihi = i;
  71     else
  72       ilo = i;
  73   }
  74
  75   return ilo;
  76 }
  77 #endif /* HAVE_INLINE */
  78
  79
  80 #endif /* __GSL_INTERP_BSEARCH_H__ */