1 /*
2  * 3-1. Our binary search makes two tests inside the loop, when one would
3  * suffice (at the price of more tests outside). Write a version with only
4  * one test inside the loop and measure the difference in run time.
5  */
6 
7 #include <stdio.h>
8 
9 main()
10 {
11 	int v[] = {1,3,6,12,27,31,32,35,39,52,91,102,103,107,109};
12 	printf ("%d: %d\n", binsearch(103, v, 15), 12);
13 	printf ("%d: %d\n", binsearch(31, v, 15), 5);
14 }
15 
16 int binsearch(int x, int v[], int n)
17 {
18 	int low, high, mid;
19 
20 	low = 0;
21 	high = n - 1;
22 	while (low < high) {
23 		mid = (low+high)/2;
24 		if (x < v[mid])
25 			high = mid - 1;
26 		else
27 			low = mid;
28 	}
29 	if (x == v[mid])
30 		return mid;
31 	return -1;
32 }
33 /*
34 int binsearch(int x, int v[], int n)
35 {
36 	int low, high, mid;
37 
38 	low = 0;
39 	high = n - 1;
40 	while (low <= high) {
41 		mid = (low+high)/2;
42 		if (x < v[mid])
43 			high = mid - 1;
44 		else if (x > v[mid])
45 			low = mid + 1;
46 		else
47 			return mid;
48 	}
49 	return -1;
50 }
51 */