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