/* Programmed by Kurt Normark, April 2003 */
#include <stdio.h>
int look_up_from_to(int v, int a[], int from, int to);
/* Search for v in the sorted array a which holds n elements.
Return index of v, of -1 if v is not found */
int look_up(int v, int a[], int n){
return look_up_from_to(v, a, 0, n-1);
}
int look_up_from_to(int v, int a[], int from, int to){
int mid = (from+to)/2;
int result;
if (from > to)
result = -1;
else if (v == a[mid])
result = mid;
else if (v < a[mid])
result = look_up_from_to(v, a, from, mid-1);
else
result = look_up_from_to(v, a, mid+1, to);
return result;
}
int main(void) {
int tab[] = {-33, -15, -7, 3, 7, 9, 10, 17, 24, 33};
int tab_size = sizeof(tab)/sizeof(int);
int search_el, result_index, i;
printf("The table: ");
for(i=0; i < tab_size; i++) printf("%5i", tab[i]);
printf("\n\n");
do{
printf("Search for which integer element (for exit: 0): ");
scanf("%i", &search_el);
if (search_el != 0){
result_index = look_up(search_el, tab, tab_size);
printf("Search result: %i\n", result_index);
}
}
while (search_el != 0);
return 0;
}
 | In this dissection we explain a binary search function that works on a sorted array of integers. In this version of the program we assume that the array is already sorted; Thus, we do not need to call any sorting function. We also, somewhat foolish, assume that 0 is not an element in the array. |
| int look_up(int v, int a[], int n){
return look_up_from_to(v, a, 0, n-1);
} |
The function look_up takes the element to look for(v) the array (a), and the number of elements in the array (n) as parameters. As it is convenient to work on sections of the array, we call a helping function look_up_from_to with v, a, and from and to indexes. At top level, from is 0 and to is n-1. |
| int look_up_from_to(int v, int a[], int from, int to){
int mid = (from+to)/2;
int result;
if (from > to)
result = -1;
else if (v == a[mid])
result = mid;
else if (v < a[mid])
result = look_up_from_to(v, a, from, mid-1);
else
result = look_up_from_to(v, a, mid+1, to);
return result;
} |
The function look_up_from_to does the real work. First we calculate the mid point of from and to, and call it mid. Next, we encounter an if-else chain. If the vaulues of from and to have passed each other, we conclude that v is not found, and we return -1. If we are lucky to find v in a[mid] the mid index is the result. Now recall that we have assumed that the elements in the array a are sorted in increasing order. If v < a[mid] we have to search for v in the interval a[from, mid-1]. This is done recursively, because we are faced with a problem similar to the enclosing problem. If v > a[mid] we have to search for v in the interval a[mid+1, to], and again recursion is used. Notice that if from == to, and if v is still not found, the new from and to limits will cross. Thus, the next recursive activation of look_up_from_to will return -1. |
|
do{
printf("Search for which integer element (for exit: 0): ");
scanf("%i", &search_el);
if (search_el != 0){
result_index = look_up(search_el, tab, tab_size);
printf("Search result: %i\n", result_index);
}
}
while (search_el != 0);
return 0;
} |
In the main function first print the table, which is pre-sorted in our version of the program. The we enter a dialogue in which we prompt the user for a value to search for. We print the result of the look up. |