commit - 4731e82242fc33696c98d8788691e6fa3c732340
commit + 328c5416b4f9e108c66c4230f84140283565ebd4
blob - /dev/null
blob + ca19881267ff01bc05d1074603939b615e1e8054 (mode 644)
--- /dev/null
+++ 3-1-input
@@ -0,0 +1,101 @@
+60
+0
+0
+0
+1
+4
+4
+4
+6
+7
+8
+9
+10
+10
+11
+11
+12
+12
+15
+18
+19
+19
+20
+23
+25
+25
+26
+29
+29
+29
+31
+31
+31
+31
+33
+34
+34
+34
+35
+36
+36
+37
+37
+37
+38
+38
+39
+39
+40
+40
+40
+41
+42
+42
+43
+43
+44
+45
+46
+49
+52
+53
+54
+57
+59
+60
+62
+62
+64
+65
+66
+66
+69
+71
+74
+74
+74
+76
+76
+78
+82
+84
+85
+85
+86
+87
+90
+90
+90
+93
+94
+94
+95
+95
+96
+97
+98
+98
+98
+99
+99
blob - /dev/null
blob + 2e42cae8ee8a694673c6c6f5bea6b2ccccff60bc (mode 644)
--- /dev/null
+++ 3-1.c
@@ -0,0 +1,61 @@
+/* 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. */
+
+#include <stdio.h>
+
+#define MAXSIZE 100
+
+int binsearch(int x, int v[], int n);
+
+int main() {
+	int needle = 0;
+	int haystack[MAXSIZE];
+	int i;
+	if (scanf("%d\n", &needle) != 1) {
+		printf("Input must be one number per line, the first number is the needle\n");
+		return 1;
+	}
+	while(scanf("%d\n", &haystack[i++]) == 1)
+		;
+	printf("Needle %d found in haystack at index %d\n", needle, binsrch(needle, haystack, i));
+	/* note the index is 2 less than line number */
+}
+
+/* binsrch: find x in v[0] <= v[1] <= ... <= v[n-1] */
+int binsrch(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;
+	}
+	/* low == high */
+	if (x == v[low])
+		return low;
+	else
+		return -1; /* no match */
+}
+
+/* binsearch: find x in v[0] <= v[1] <= ... <= v[n-1] */
+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 - 1;
+		else if (x > v[mid])
+			low = mid + 1;
+		else /* found match */
+			return mid;
+	}
+	return -1; /* no match */
+}