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;
}
``````