Exercise 3.01

Page 58

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 LEN 6

int binsearch(int x, int v[], int n);
int binsearch2(int x, int v[], int n);

int main()
{
	int v[LEN] = { 1, 2, 4, 8, 16, 32 };

	/* 3ms total for the 4 calculations 
	 * printf("Original function:\n"); 
	 * printf("2 occurs at %d\n", binsearch(2, v, LEN)); 
	 * printf("3 occurs at %d\n", binsearch(3, v, LEN)); 
	 * printf("12 occurs at %d\n", binsearch(12, v, LEN)); 
	 * printf("16 occurs at %d\n", binsearch(16, v, LEN)); */

	/* 1ms total for the 4 calculations */
	printf("\nModified function:\n");
	printf("2 occurs at %d\n", binsearch2(2, v, LEN));
	printf("3 occurs at %d\n", binsearch2(3, v, LEN));
	printf("12 occurs at %d\n", binsearch2(12, v, LEN));
	printf("16 occurs at %d\n", binsearch2(16, v, LEN));
}

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
			return mid;
	}
	return -1;
}

int binsearch2(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;
	}

	return x == v[low] ? low : -1;
}