+
+template<class T>
+void
+binary_search_bounds (Array<T> const &table,
+ T const &key, int (*compare) (T const&, T const &),
+ int *lo,
+ int *hi)
+{
+ int cmp;
+ int result;
+
+ /* binary search */
+ do
+ {
+ cmp = (*lo + *hi) / 2;
+
+ result = (*compare) (key, table[cmp]);
+
+ if (result < 0)
+ *hi = cmp;
+ else
+ *lo = cmp;
+ }
+ while (*hi - *lo > 1);
+}
+
+
+/*
+ lookup with binsearch, return array index.
+*/
+template<class T>
+int
+binary_search (Array<T> const &table,
+ T const &key, int (*compare) (T const&, T const &),
+ int lo = 0,
+ int hi = -1
+ )
+{
+ if (hi < 0)
+ hi = table.size ();
+
+ binary_search_bounds (table, key, compare, &lo, &hi);
+
+ if (! (*compare) (key, table[lo]))
+ {
+ return lo;
+ }
+ else
+ return -1; /* not found */
+}