Merge commit '23c7930d27fe11c4655e1291a07a821dbbaba78d' as 'funtools'

1 files changed, 68 insertions, 0 deletions

diff --git a/funtools/bsearch.c b/funtools/bsearch.c
new file mode 100644
index 0000000..df69ca2
--- /dev/null
+++ b/funtools/bsearch.c
@@ -0,0 +1,68 @@
+/* http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary */
+
+/* returns first target if more than one have same value */
+static public int search(int [] array, int target)
+{
+  int high = array.length, low = -1, probe;
+  while (high - low > 1)
+    {
+      probe = (high + low) / 2;
+      if (array[probe] < target)
+	low = probe;
+      else
+	high = probe;
+    }
+  if (high == array.length || array[high] != target)
+    return -1;
+  else
+    return high;
+}
+
+/* returns last target if more than one have same value */
+static public int search2(int [] array, int target)
+{
+  int high = array.length, low = -1, probe;
+  while (high - low > 1)
+    {
+      probe = (high + low) / 2;
+      if (array[probe] > target)
+	high = probe;
+      else
+	low = probe;
+    }
+  if (low == -1 || array[low] != target)
+    return -1;
+  else
+    return low;
+}
+
+static public int [] range(int [] array, int floor, int ceiling)
+{
+  int [] answer = new int[2];
+  int high, low, probe;
+
+  // work on floor
+  high = array.length; low = -1;
+  while (high - low > 1)
+    {
+      probe = (high + low) / 2;
+      if (array[probe] < floor)
+	low = probe;
+      else
+	high = probe;
+    }
+  answer[0] = low;
+
+  // work on ceiling
+  high = array.length; low = -1;
+  while (high - low > 1)
+    {
+      probe = (high + low) / 2;
+      if (array[probe] > ceiling)
+	high = probe;
+      else
+	low = probe;
+    }
+  answer[1] = high;
+  return answer;
+}