Mastering Algorithms With C - Kyle Loudon [142]
/**************************************************************************
* *
* Adjust each count to reflect the counts before it. *
* *
**************************************************************************/
for (i = 1; i < k; i++)
counts[i] = counts[i] + counts[i - 1];
/**************************************************************************
* *
* Use the counts to position each element where it belongs. *
* *
**************************************************************************/
for (j = size - 1; j >= 0; j--) {
index = (int)(data[j] / pval) % k;
temp[counts[index] - 1] = data[j];
counts[index] = counts[index] - 1;
}
/**************************************************************************
* *
* Prepare to pass back the data as sorted thus far. *
* *
**************************************************************************/
memcpy(data, temp, size * sizeof(int));
}
/*****************************************************************************
* *
* Free the storage allocated for sorting. *
* *
*****************************************************************************/
free(counts);
free(temp);
return 0;
}
Description of Binary Search
Binary search is a technique for searching that works similarly to how we might systematically guess numbers in a guessing game. For example, suppose someone tells us to guess a number between and 99. The consistently best approach is to begin with 49, the number in the middle of and 99. If 49 is too high, we try 24, the number in the middle of the lower half of to 99 (0 to 48). Otherwise, if 49 is too low, we try 74, the number in the middle of the upper half of to 99 (50 to 99). We repeat this process for each narrowed range until we guess right.
Binary search begins with a set of data that is sorted. To start the search, we inspect the middle element of the sorted set. If the element is greater than the one we are looking for, we let the lower half of the set be the new set to search. Otherwise, if the element is less, we let the upper half be the new set. We repeat this process on each smaller set until we either locate the element we are looking for or cannot divide the set any further.
Binary search works with any type of data provided we can establish an ordering among the elements. It is a simple algorithm, but as you might suspect, its reliance on sorted data makes it inefficient for sets in which there are frequent insertions and deletions. This is because for each insertion or deletion, we must ensure that the set stays sorted for the search to work properly. Keeping a set sorted is expensive relative to searching it. Also, elements must be in contiguous storage. Thus, binary search is best utilized when the set to be searched is relatively static.
Interface for Binary Search
Name
bisearch
Synopsis
int bisearch(void *sorted, void *target, int size, int esize,
int (*compare)(const void *key1, const void *key2);
Return Value
Index of the target if found, or -1 otherwise.
Description
Uses binary search to locate target in sorted, a sorted array of elements. The number of elements in sorted is specified by size. The size of each element is specified by esize. The function pointer compare specifies a user-defined function to compare elements. This function should return 1 if key1 > key2, if key1 = key2, and -1 if key1 < key2.
Complexity
O (lg n), where n is the number of elements to be searched.
Implementation and Analysis of Binary Search
Binary search works fundamentally by dividing a sorted set of data repeatedly and inspecting the element in the middle of each division. In the implementation presented here, the sorted set of data resides in sorted, a single block of contiguous storage. The argument target is the data we are searching for.
This implementation revolves around a single loop controlled by the variables left and right, which define the boundaries of the current set in which we are focusing our search (see Example 12.8). Initially, we set left and right