/ray/src/lib/tl/binsearch.h

Go to the documentation of this file.

/*
 * lib/tl/binsearch.h 
 * 
 * Binary search templates. 
 * 
 * Copyright (c) 2004 by Wolfgang Wieser ] wwieser (a) gmx <*> de [ 
 * 
 * This file may be distributed and/or modified under the terms of the 
 * GNU General Public License version 2 as published by the Free Software 
 * Foundation. (See COPYING.GPL for details.)
 * 
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 * 
 */

#ifndef _TemplateLibrary_BINARYSEARCH_H_
#define _TemplateLibrary_BINARYSEARCH_H_ 1

#include <lib/sconfig.h>    /* MUST be first */

#include <lib/tl/defop.h>


template<typename T,typename K>ssize_t BinarySearch(const T *arr,size_t nelem,
    const K &key)
{
    if(!nelem)  return(-1);
    size_t a=0,b=nelem-1;
    while(b-a>1)
    {  size_t m=(a+b)/2;  (arr[m]<key) ? a=m : b=m;  }
    if(arr[a]==key)  return(a);
    if(b!=a && arr[b]==key)  return(b);
    return(-1);
}


template<typename T,typename K,typename _OP>ssize_t TLBinarySearch(
    const T *_arr,size_t nelem,
    const K &key,
    const _OP &op=TLDefaultOperators_CDT<T>())
{
    if(!nelem)  return(-1);
    size_t a=0,b=nelem-1;
    while(b-a>1)
    {  size_t m=(a+b)/2;  op.lt(op.idx(_arr,m),key) ? a=m : b=m;  }
    if(op.eq(op.idx(_arr,a),key))  return(a);
    if(b!=a && op.eq(op.idx(_arr,b),key))  return(b);
    return(-1);
}


template<typename T,typename K>bool BinarySearch(const T *arr,size_t nelem,
    const K &key,size_t *ret_idx)
{
    if(nelem<=1) {  if(!nelem)  {  *ret_idx=0;  return(0);  }
                    if(key>arr[0])  {  *ret_idx=1;  return(0);  }
                    *ret_idx=0;  return(key==arr[0]);  }
    size_t a=0,b=--nelem;  // NOTE: nelem decreased by 1!
    while(b-a>1)  {  size_t m=(a+b)/2;  (arr[m]<key) ? a=m : b=m;  }
    if(!a && key<arr[0])  {  *ret_idx=0;  return(0);  }
    if(b==nelem && key>arr[nelem])  {  *ret_idx=nelem+1;  return(0);  }
    if(key==arr[a])  {  *ret_idx=a;  return(1);  }
    *ret_idx=b;  return(b && key==arr[b]);
}


template<typename T,typename K,typename _OP>bool TLBinarySearch(
    const T *_arr,size_t nelem,
    const K &key,size_t *ret_idx,
    const _OP &op=TLDefaultOperators_CDT<T>())
{
    if(nelem<=1)
    {
        if(!nelem)  {  *ret_idx=0;  return(0);  }
        if(op.lt(op.idx(_arr,0),key))  { *ret_idx=1;  return(0);  }
        *ret_idx=0;  return(op.eq(op.idx(_arr,0),key));
    }
    size_t a=0,b=--nelem;  // NOTE: nelem decreased by 1!
    while(b-a>1)
    {  size_t m=(a+b)/2; op.lt(op.idx(_arr,m),key) ? a=m : b=m;  }
    if(!a && op.gt(op.idx(_arr,0),key))  {  *ret_idx=0;  return(0);  }
    if(b==nelem && op.lt(op.idx(_arr,nelem),key))
        { *ret_idx=nelem+1; return(0); }
    if(op.eq(op.idx(_arr,a),key))  {  *ret_idx=a;  return(1);  }
    *ret_idx=b;  return(b && op.eq(op.idx(_arr,b),key));
}

#endif  /* _TemplateLibrary_BINARYSEARCH_H_ */

---