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.
#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
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
#include <stdio.h> // for getchar(), putchar(), printf(), EOF
// count types of characters: digits, whitespace, other
int main()
{
int c, i, nwhite, nother, ndigit[10];
nwhite = nother = 0; // initialize
for (i = 0; i < 10; i++)
{ndigit[i] = 0;} // initialize
while ((c = getchar()) != EOF)
{
switch(c)
{
case '0' : case '1': case '2' : case '3' : case '4' :
case '5' : case '6': case '7' : case '8' : case '9' :
ndigit[c-'0']++;
break; // without break, execution continues to the remaining cases
case ' ' : case '\t' : case '\n' :
nwhite++;
break;
default: // for all the other characters (possible cases)
nother++;
break; // optional break of the end
}
}
printf("digits:\t\t");
for (i = 0; i < 10; i++)
{printf("%d\t", i);}
putchar('\n');
printf("occurrences:\t");
for (i = 0; i < 10; i++)
{printf("%d\t", ndigit[i]);}
putchar('\n');
printf("whitespaces:\t%d\n", nwhite);
printf("others:\t\t%d\n", nother);
return 0;
}
/*
gcc count.c -o count
./count // input from keyboard
// type the input, then press CTRL+D in Linux, CTRL+Z, then Enter in Windows (EOF)
./count < count.c // input from source file
digits: 0 1 2 3 4 5 6 7 8 9
occurrences: 17 22 4 6 3 5 7 6 8 4
whitespaces: 645
others: 966
./count < count // input from binary file
digits: 0 1 2 3 4 5 6 7 8 9
occurrences: 18 7 16 3 8 8 7 1 16 5
whitespaces: 70
others: 16681
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
Exercise 3-2. Write a function escape(s,t) that converts characters like newline and tab into visible escape sequences like \n and \t as it copies the string t to s. Use a switch. Write a function for the other direction as well, converting escape sequences into the real characters.
#include <stdio.h> // for printf()
#define SIZE 100 // array size
void escape(char s[], char t[]); // copy t[] to s[] making escapes visible
void unescape(char s[], char t[]); // copy t[] to s[] doing the opposite
int main()
{
char s[SIZE];
char t[SIZE] = "\', \", \t, \n, \r, \f, \v, \a, \b, \\, etc.";
printf("String with escapes: %s\n", t);
escape(s,t);
printf("Visible escapes: %s\n", s);
unescape(t,s);
printf("Real characters: %s\n", t);
return 0;
}
void escape(char s[], char t[]) // copy t[] to s[] making escapes visible
{
int i, j = 0;
for (i = 0; t[i] != '\0'; i++)
{
switch(t[i])
{
case '\'' :
s[j++] = '\\'; s[j++] = '\'';
break;
case '\"' :
s[j++] = '\\'; s[j++] = '\"';
break;
case '\t' :
s[j++] = '\\'; s[j++] = 't';
break;
case '\n' :
s[j++] = '\\'; s[j++] = 'n';
break;
case '\r' :
s[j++] = '\\'; s[j++] = 'r';
break;
case '\f' :
s[j++] = '\\'; s[j++] = 'f';
break;
case '\v' :
s[j++] = '\\'; s[j++] = 'v';
break;
case '\a' :
s[j++] = '\\'; s[j++] = 'a';
break;
case '\b' :
s[j++] = '\\'; s[j++] = 'b';
break;
case '\\' :
s[j++] = '\\'; s[j++] = '\\';
break;
default:
s[j++] = t[i]; // copy non-escapes
break;
}
}
s[j] = '\0'; // properly end string
}
void unescape(char s[], char t[]) // copy t[] to s[] turning \t into tab, etc.
{
int i, j = 0;
for (i = 0; t[i] != '\0'; i++)
{
switch(t[i])
{
case '\\' :
switch(t[i+1])
{
case '\'' : case '\"' : case '\\' :
s[j++] = t[i+1];
i++;
break;
case 't' :
s[j++] = '\t';
i++;
break;
case 'n' :
s[j++] = '\n';
i++;
break;
case 'r' :
s[j++] = '\r';
i++;
break;
case 'f' :
s[j++] = '\f';
i++;
break;
case 'v' :
s[j++] = '\v';
i++;
break;
case 'a' :
s[j++] = '\a';
i++;
break;
case 'b' :
s[j++] = '\b';
i++;
break;
default:
s[j++] = t[i];
break;
}
break;
default:
s[j++] = t[i];
break;
}
}
s[j] = '\0'; // properly end string
}
/*
gcc escapes.c -o escapes
./escapes
String with escapes: ', ", ,
,
,
, ,, \, etc.
Visible escapes: \', \", \t, \n, \r, \f, \v, \a, \b, \\, etc.
Real characters: ', ", ,
,
,
, ,, \, etc.
*/