implement binary search

1 files changed, 19 insertions, 0 deletions

diff --git a/sorts.c b/sorts.c
index a03dd68..0207fd0 100644
--- a/sorts.c
+++ b/sorts.c
@@ -29,7 +29,26 @@ int *mk_rand_arr(int, int);
 void mergesort(int *, int, int);
 void merge(int *, int, int, int);
 void shell_sort(int *, int);
+int binary_search(int *, int, int, int);
 
+int binary_search(int *a, int low, int high, int target)
+{
+    while (low <= high)
+    {
+        int middle = low + (high - low) / 2;
+
+        if (target < a[middle])
+            high = middle - 1;
+        else if (target > a[middle])
+            low = middle + 1;
+        else
+            return middle;
+    }
+
+    return -1;
+}
+
+/* pg 62, k&r 2nd ANSI, running T(N) = O(N^3/2) */
 void shell_sort(int *v, int n)
 {
     int gap, i, j, temp;