From 3e4c2b79987a583d4ac00192eb6ac0cfb3b53997 Mon Sep 17 00:00:00 2001
From: Adam Carpenter <gitlab@53hor.net>
Date: Tue, 23 Jul 2019 13:43:29 -0400
Subject: Finished 3-1.

---
 ch3/3-1.c | 50 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 50 insertions(+)
 create mode 100644 ch3/3-1.c

(limited to 'ch3')

diff --git a/ch3/3-1.c b/ch3/3-1.c
new file mode 100644
index 0000000..0dea28e
--- /dev/null
+++ b/ch3/3-1.c
@@ -0,0 +1,50 @@
+#include <stdio.h>
+
+int binsearch(int x, int v[], int n);
+int binsearch_original(int x, int v[], int n);
+
+int main() {
+    int v[] = {1,2,3,4,5};
+    int x = 2;
+    int n = 5;
+    printf("%d\n%d\n", binsearch_original(x, v, n), binsearch(x, v, n));
+}
+
+int binsearch(int x, int v[], int n) {
+    int low, high, mid;
+
+    low = 0;
+    high = n - 1;
+
+    while (low < high) {
+        mid = (low + high) / 2;
+        if (x <= v[mid])
+            high = mid;
+        else
+            low = mid + 1;
+    }
+
+    return (x == v[low]) ? low : -1;
+}
+
+/*
+ * Find x in v[0] <= v[1] <= ... <= v[n-1]
+ */
+int binsearch_original(int x, int v[], int n) {
+    int low, high, mid;
+
+    low = 0;
+    high = n - 1;
+
+    while (low <= high) {
+        mid = (low + high) / 2;
+        if (x < v[mid])
+            high = mid - 1;
+        else if (x > v[mid])
+            low = mid + 1;
+        else // found match
+            return mid;
+    }
+
+    return -1; // no match
+}
-- 
cgit v1.2.3