Solve Exercise 3-1: binsearch2

1 files changed, 71 insertions, 0 deletions

diff --git a/ch3/3-01_binsearch2.c b/ch3/3-01_binsearch2.c
new file mode 100644
index 0000000..bcd66c3
--- /dev/null
+++ b/ch3/3-01_binsearch2.c
@@ -0,0 +1,71 @@
+#include <stdio.h>
+
+/* The C Programming Language: 2nd Edition
+ *
+ * Exercise 3-1: Our binary search makes two tests inside the loop, when
+ * one would suffice (at the price of more tests outside). Write a version
+ * with only one test inside the loop and measure the difference in run-
+ * time.
+ *
+ * Answer: I don't know how to measure the performance of the original
+ * function. `time` reports 0.001 sec, so it's not precise enough.
+ *
+ * Anyway, the trick is to create a loop that will exit on two conditions:
+ * either the last-inspected integer in the array matches the one we're
+ * looking for, or it doesn't. The only issue with this is it won't exit
+ * the loop as soon as it's found; it may take a few more iterations for it
+ * to fully exit, where it will determine which condition made it exit.
+ *
+ * I don't have a good tool to measure execution time with (that I know of), so
+ * my best guess is binsearch2 is faster because it uses only one test in the
+ * while loop. However, it won't exit the loop as soon as the match is found; it
+ * needs another few iterations for 'low' to equal or surpass 'high'.
+ */
+
+int binsearch(int x, int v[], int n) {
+	int low, mid, high;
+
+	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 {
+			return mid;
+		}
+	}
+	return -1;
+}
+
+int binsearch2(int x, int v[], int n) {
+	int low, mid, high;
+
+	low = 0;
+	high = n - 1;
+
+	while (low < high) {
+		mid = (low + high) / 2;
+		if (x <= v[mid]) {
+			high = mid;
+		} else {
+			low = mid + 1;
+		}
+	}
+
+	if (x == v[low]) {
+		return low;
+	} else {
+		return -1;
+	}
+}
+
+int main() {
+	int foo[5] = {1, 2, 3, 5, 6};
+	int i;
+	for (i = 1; i < 7; i++) {
+		printf("binsearch2 for %d is %d\n", i, binsearch2(i, foo, 5));
+	}
+}