bin_search.t

来自「A Library of Efficient Data Types and Al」· T 代码 · 共 61 行

/*******************************************************************************
+
+  LEDA 4.5  
+
+
+  bin_search.t
+
+
+  Copyright (c) 1995-2004
+  by Algorithmic Solutions Software GmbH
+  All rights reserved.
+ 
*******************************************************************************/

// $Revision: 1.3 $  $Date: 2004/02/06 11:20:04 $

#ifndef LEDA_BINSEARCH_T
#define LEDA_BINSEARCH_T

LEDA_BEGIN_NAMESPACE



template <class E>
inline E* BINARY_SEARCH_C(E* l, E* r, const E& x)
{ while (l <= r)
  { E* m = l + (r-l)/2;
    int c = compare(x,*m);
    if (c == 0) return m;
    if (c > 0)
       l = m + 1;
    else
       r = m - 1;
   }
  return r;
}


template <class ARRAY, class E>
inline int BINARY_SEARCH_ARR(const ARRAY &arr, const E& x)
{ GenPtr* A = (GenPtr*)arr.first_item();
  GenPtr* l = A;
  GenPtr* r = A + arr.size() - 1;
  while (l <= r)
  { GenPtr* m = l + (r-l)/2;
    int c = compare(x,LEDA_ACCESS(E,*m));
    if (c == 0) return arr.low() + (m-A);
    if (c > 0)
       l = m + 1;
    else
       r = m - 1;
   }
  return arr.low() + (r-A);
}


LEDA_END_NAMESPACE

#endif