Binary Search
Binary Search is an algorithm that provides faster search when we are looking for an element in a sorted array. Like the case of searching a binary search tree, at each step we eliminate half of the nodes leaving us only half elements to search in the next step. This elimination at each step leads to faster lookup.
In binary search, we start by looking at the two extreme indices of the array: for an array with N elements, index 0 serves as the lower limit and index (N-1) serves as the higher limit. In the next step, we go to the middle of the current range that is (0 + (N-1))/2. If the value that needs to be searched is greater than the middle value, then we focus on the range spanning from the middle point to the end point. In this case, the middle point becomes the new lower limit. On the other hand, if the value that needs to be searched is lower than the middle value, then we focus on the range spanning from the start of the array till the middle point. In this case, the middle point becomes the new higher limit. Since we drop half of the elements at each step, the time-complexity of this step is O(logN).
Let us explain this further using the figure below. We start with a sorted array and search for 20 in this array. Initially, the lower and higher limits are the first and the last value of the array (which are 4 and 98) respectively; the middle point (index) is (0+14)/2 or 7; the value at index 7 is 35. Since 20 is lower than the value of the middle point, the current middle point becomes the higher limit. We keep adjusting the lower and higher limits until we find the index with value 20.
Figure: Binary Search (Searching for 20)
Implementation
Now that we understand the basics of binary search, let us provide a simple implementation and use its output to demonstrate the search process. We provide the implementation below.
#include <stdio.h>
#include <stdlib.h>
#define SIZE_OF_BLOCK_ALLOCATION 10
/* The global ones! */
int *binarysearch_array = NULL;
int binarysearch_size = 0;
int binarysearch_next_element = 0;
void binarysearch_print () {
int counter = 0;
if (binarysearch_array == NULL) {
return;
}
printf("Array: ");
for (counter = 0; counter < binarysearch_next_element; counter++) {
printf("%d ", binarysearch_array[counter]);
}
printf("\n");
}
/* Insert a value into a sorted array */
void binarysearch_insert (int next_element) {
int counter, inner_counter;
if (binarysearch_next_element == binarysearch_size) {
binarysearch_size += SIZE_OF_BLOCK_ALLOCATION;
binarysearch_array =
(void*)realloc(binarysearch_array, binarysearch_size * sizeof(int));
/* Handle the case when malloc fails */
}
/* Temporarily place the node in the last place */
binarysearch_array[binarysearch_next_element] = next_element;
binarysearch_next_element++;
for (counter = 0; counter < binarysearch_next_element; counter++) {
if (binarysearch_array[counter] > next_element) {
for (inner_counter = binarysearch_next_element;
inner_counter > counter;
inner_counter--) {
binarysearch_array[inner_counter] =
binarysearch_array[inner_counter -1];
}
binarysearch_array[counter] = next_element;
return;
}
}
}
int binarysearch_search (int search_value) {
int counter = 0, index_low = 0;
int index_high = binarysearch_next_element -1;
printf("\nSearching for %d\n", search_value);
if (binarysearch_array == NULL) {
return -1;
}
if (binarysearch_array[index_low] == search_value) {
return index_low;
}
if (binarysearch_array[index_high] == search_value) {
return index_high;
}
while (index_low < index_high) {
counter = (index_low + index_high)/2;
printf("[Current Pass: index_low: %d index_high: %d] Mid-point: %d\n",
index_low, index_high, binarysearch_array[counter]);
if ((counter == index_low) || (counter == index_high)) {
return -1;
}
if (binarysearch_array[counter] == search_value) {
return counter;
}
if (search_value > binarysearch_array[counter]) {
index_low = counter;
} else {
index_high = counter;
}
}
return -1;
}
void binarysearch_delete (int delete_value) {
int index, counter, inner_counter, temp_val;
index = binarysearch_search(delete_value);
if (index == -1) {
printf("The node to be deleted does not exist \n");
return;
} else {
printf("The node to be deleted exists (counter: %d) \n", index);
}
for (counter=index; counter < binarysearch_next_element; counter++) {
binarysearch_array[counter] = binarysearch_array[counter+1];
}
binarysearch_next_element--;
}
int main (int argc, char *argv[]) {
int input_array[] = {80, 5, 98, 15, 30, 20, 35, 4, 45, 65, 10, 58, 50, 40, 25};
int len = sizeof(input_array)/sizeof(input_array[0]);
int ret_index, i;
for (i = 0; i < len; i++) {
binarysearch_insert(input_array[i]);
}
binarysearch_print();
ret_index = binarysearch_search(20);
printf("The passed value exist at index: %d\n", ret_index);
ret_index = binarysearch_search(15);
printf("The passed value exist at index: %d\n", ret_index);
binarysearch_delete(20);
binarysearch_print();
ret_index = binarysearch_search(20);
printf("The passed value exist at index: %d\n", ret_index);
free(binarysearch_array);
return 0;
}
Let us now go over the above implementation.
The implementation begins with a simple function: binarysearch_print() that prints the array. Following that, we have the binarysearch_insert() function. This function inserts a node in a sorted fashion. The current node is inserted at the end and then we find the point where we need to insert the new element in the already sorted element. Once we find the first element that is greater than the passed index, we shift all the elements beyond this element by one and thus, make room for the current element. Needless to say, this is an expensive operation. Next, we copy the current element in that position.
However, there are cases when the elements of the binary array is fixed and hence, there is no need for dynamically inserting (or deleting, for that matter) the element: a case being that of a text-comparison. Given a set of text-tokens, comparing if the new text belongs to the existing set of tokens. This can be used for doing auto-fill (guessing what the user wants to type) or for spell-check. In such cases, the overhead of the input element can be done offline. Thus, once, the table of tokens is ready, there is no further cost of inserting a new element. For the sake of completeness, we also provide a function, binarysearch_delete() that deletes an element from the binary search array.
The next function is binarysearch_search() which is the heart of this algorithm. Given a search value, we can use this function to locate this element. If found, we return the index of this element. The logic is simple: we use two counters to continuously narrow down the range in which the element is likely to exist. These counters are: index_low and index_high. These are set to 0 and (N-1) (which is binarysearch_last_element -1). In each round, we get the middle point of these two limits (counters), counter and then compare the value of the element sitting at the middle point. If the value to be searched is more than the value of the element sitting at the middle point, we shift our search in the second half of the current range; we do this by setting the index_low to the middle point (counter). On the other hand, if the value to be searched is smaller than the value of the element sitting at the middle point, we shift our search in the first half of the current range; we do this by setting the index_high to the middle point (counter).
In the end, we bring all of these elements together in the main(). The main() function uses an array (input_array) and inserts its elements into the binarysearch_array. Once added, we print the array (which should be sorted, by now!) and then do operations like search, delete, and print. Here is the compilation and output of the above program.
user@codingbison $ gcc binary_search.c -o binary_search user@codingbison $ ./binary_search Array: 4 5 10 15 20 25 30 35 40 45 50 58 65 80 98 Searching for 20 [Current Pass: index_low: 0 index_high: 14] Mid-point: 35 [Current Pass: index_low: 0 index_high: 7] Mid-point: 15 [Current Pass: index_low: 3 index_high: 7] Mid-point: 25 [Current Pass: index_low: 3 index_high: 5] Mid-point: 20 The passed value exist at index: 4 Searching for 15 [Current Pass: index_low: 0 index_high: 14] Mid-point: 35 [Current Pass: index_low: 0 index_high: 7] Mid-point: 15 The passed value exist at index: 3 Searching for 20 [Current Pass: index_low: 0 index_high: 14] Mid-point: 35 [Current Pass: index_low: 0 index_high: 7] Mid-point: 15 [Current Pass: index_low: 3 index_high: 7] Mid-point: 25 [Current Pass: index_low: 3 index_high: 5] Mid-point: 20 The node to be deleted exists (counter: 4) Array: 4 5 10 15 25 30 35 40 45 50 58 65 80 98 Searching for 20 [Current Pass: index_low: 0 index_high: 13] Mid-point: 35 [Current Pass: index_low: 0 index_high: 6] Mid-point: 15 [Current Pass: index_low: 3 index_high: 6] Mid-point: 25 [Current Pass: index_low: 3 index_high: 4] Mid-point: 15 The passed value exist at index: -1