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
---
ch3/3-01_binsearch2.c | 71 +++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 71 insertions(+)
create mode 100644 ch3/3-01_binsearch2.c
(limited to 'ch3')
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