Exercise 3-1 (binsearch - Binary search)

Chapter_3

count     Exercise_3-2

---

---

Exercise 3-1     K&R, p. 58

Exercise 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 one test inside the loop and measure the difference in run-time.

binsearch.c     K&R, p. 58         download

#include <stdio.h> // for printf()
#include <time.h> // for clock_t, clock(), CLOCKS_PER_SEC

#define SIZE 1000000 // array size

// find x in v[0] <= v[1] <= ... <= v[n-1]
int binsearch1(int x, int v[], int n);
int binsearch2(int x, int v[], int n);

int main()
{
int array[SIZE+1]; // for ending '\0'
int i;
clock_t start, end;
double time;

for (i = 0; i < SIZE; i++) // initialize array
{
array[i] = i*2;
}
array[SIZE] = '\0';

start = clock();
for (i = 0; i < 100000000; i++)
{
binsearch1(i % (SIZE*2), array, SIZE);
}
end = clock();
time = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("Execution time for binsearch1(): %f\n", time);

start = clock();
for (i = 0; i < 100000000; i++)
{
binsearch2(i % (SIZE*2), array, SIZE);
}
end = clock();
time = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("Execution time for binsearch2(): %f\n", time);

return 0;
}
// find x in v[0] <= v[1] <= ... <= v[n-1]
int binsearch1(int x, int v[], int n)
{
int low = 0, high = n-1, mid;

while (low <= high)
{
if (x < v[low] || x > v[high])
{return -1;} // not found
if (x == v[low]) {return low;} // found
if (x == v[high]) {return high;} // found
mid = (low+high)/2;

if (x < v[mid])
{high = mid-1;}
else if (x > v[mid])
{low = mid+1;}
else {return mid;} // found match
}

return -1;
}
// find x in increasingly sorted array v[] of size n
int binsearch2(int x, int v[], int n)
{
int low = 0, high = n-1, mid;

while (low < high)
{
mid = (low+high)/2;

if (x <= v[mid])
{high = mid;}
else {low = mid+1;}
}

if (x == v[high]) // found match
{return high;}

return -1;
}
/*
gcc binsearch.c -o binsearch
./binsearch // SIZE 100
Execution time for binsearch1(): 4.123659
Execution time for binsearch2(): 3.795055

gcc binsearch.c -o binsearch
./binsearch // SIZE 1000
Execution time for binsearch1(): 8.603500
Execution time for binsearch2(): 9.906994

gcc binsearch.c -o binsearch
./binsearch // SIZE 10000
Execution time for binsearch1(): 10.751878
Execution time for binsearch2(): 11.872762

gcc binsearch.c -o binsearch
./binsearch // SIZE 100000
Execution time for binsearch1(): 13.423860
Execution time for binsearch2(): 13.800940

gcc binsearch.c -o binsearch
./binsearch // SIZE 1000000
Execution time for binsearch1(): 15.837140
Execution time for binsearch2(): 16.058546
*/

Note:  Do not forget to recompile after you change the SIZE.

---

---

Chapter_3

BACK_TO_TOP

count     Exercise_3-2