summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--ch3/3-1.c50
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
+}