Finished 3-1.HEADmaster

1 files changed, 50 insertions, 0 deletions

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
+}