home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c221 / 6.ddi / MWHC.006 / C2 < prev    next >
Encoding:
Text File  |  1992-06-07  |  2.0 KB  |  79 lines
  1. #ifndef __RWTBSEARCH_H__
  2. #define __RWTBSEARCH_H__
  3. pragma push_align_members(64);
  4.  
  5. /*
  6.  * Parameterized binary search; this version allows duplicate keys
  7.  *
  8.  * $Header:   E:/vcs/rw/tbsearch.h_v   1.1   04 Mar 1992 10:16:40   KEFFER  $
  9.  *
  10.  ****************************************************************************
  11.  *
  12.  * Rogue Wave Software, Inc.
  13.  * P.O. Box 2328
  14.  * Corvallis, OR 97339
  15.  *
  16.  * Copyright (C) 1992. This software is subject to copyright 
  17.  * protection under the laws of the United States and other countries.
  18.  *
  19.  ***************************************************************************
  20.  *
  21.  * This binary search routine differs from the ANSI C version.
  22.  * 1) If duplicate items exist, it returns the index of the first instance.
  23.  * 2) If an item is not in the table, it returns the index where it
  24.  *    should be inserted.  Hence, it is useful for insertion sorts.
  25.  *
  26.  ***************************************************************************
  27.  *
  28.  * $Log:   E:/vcs/rw/tbsearch.h_v  $
  29.  * 
  30.  *    Rev 1.1   04 Mar 1992 10:16:40   KEFFER
  31.  *  
  32.  * 
  33.  *    Rev 1.0   02 Mar 1992 16:10:50   KEFFER
  34.  * Initial revision.
  35.  */
  36.  
  37. #ifndef __RWDEFS_H__
  38. #  include "rw/defs.h"
  39. #endif
  40.  
  41. STARTWRAP
  42. #include <stdlib.h>
  43. ENDWRAP
  44.  
  45. template <class T> int
  46. RWTbsearch(T key, const T* base, unsigned nelem)
  47. {
  48.   if (nelem==0) return 0;
  49.   int top = nelem - 1;
  50.   int bottom = 0;
  51.   int middle;
  52.  
  53.   while (top>bottom) {
  54.     middle = (top+bottom) >> 1;
  55.     if ( *(base+middle) < key)
  56.       bottom = middle + 1;
  57.     else
  58.       top = middle;
  59.   }
  60.  
  61.   if ( *(base+top) == key ){
  62.     // Found it.  Now search downwards for the first instance.
  63.     while ( top && *(base+top-1) == key ) --top;
  64.   }
  65.   else {
  66.     // Not found; Search for where it should be inserted.
  67.     while (top < nelem && *(base+top)< key) ++top;
  68.   }
  69.   return top;
  70. }
  71.  
  72. template <class T> inline int
  73. RWTbsearch(T key, const T* base, const unsigned nelem){
  74.     RWTbsearch(key, base, (unsigned)nelem);
  75.     }
  76.     
  77. pragma pop_align_members();
  78. #endif    /* __RWTBSEARCH_H__ */
  79.