From 736bbc64f2b0af4faead40be3dc98ebe7f9fcbff Mon Sep 17 00:00:00 2001
From: zlg <zlg@zlg.space>
Date: Tue, 16 Apr 2013 00:53:42 -0500
Subject: Solve Exercise 3-1: binsearch2

---
 ch2/2-10_lower.c      |  2 +-
 ch3/3-01_binsearch2.c | 71 +++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 72 insertions(+), 1 deletion(-)
 create mode 100644 ch3/3-01_binsearch2.c

diff --git a/ch2/2-10_lower.c b/ch2/2-10_lower.c
index fe0288b..44cdde7 100644
--- a/ch2/2-10_lower.c
+++ b/ch2/2-10_lower.c
@@ -15,6 +15,6 @@ int lower(int c) {
 
 int main() {
 	char foo = 'F';
-	printf("The follow letter should be lowercase: %c\n", lower(foo));
+	printf("The following letter should be lowercase: %c\n", lower(foo));
 	return 0;
 }
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));
+	}
+}
-- 
cgit v1.2.3-54-g00ecf