Binary Search Algorithm - C Programming Example

A binary search algorithm is a search algorithm that finds the position of searched value within the array. In the binary search algorithm, the element in the middle of the array is checked each time for the searched element to be found. If the middle element is not equal to the searched element, the search is repeated in the other half of the searched element. In this way, the search space is halved at each step.

The binary search algorithm works on sorted arrays. For non-sorted arrays, the array must first be sorted by any sorting algorithm in order to make a binary search.

The steps of binary search algorithm:

1- Select the element in the middle of the array.

2- Compare the selected element to the searched element, if it is equal to the searched element, terminate.

3- If the searched element is larger than the selected element, repeat the search operation in the major part of the selected element.

4- If the searched element is smaller than the selected element, repeat the search in the smaller part of the selected element.

5- Repeat the steps until the smallest index in the search space is less than or equal to the largest index.

For example; 2,3,4,5,6,7,8,9,22,33,45.

The following steps will be followed to find the number 4 with binary search in a sequential array of these numbers.

The middle element of the array is selected as 7 and compared with the searched element 4. The searched element (4) is not equal to the middle element (7), the part at the center of the array which is less than 7.

Our new search array: 2,3,4,5,6.

The middle element of our new search array is 4 and the search is completed.

With binary search algorithm, it is possible to find the searched value to log2N comparisons in an N-element array.

A sample C code will be as follows if we try to implement the binary search algorithm in a sequential array as in the example.

C Example:

#include <stdio.h>
int main()
{
    int array[11] = {2,3,4,5,6,7,8,9,22,33,45};
    int low       = 0;
    int high      = 10;
    int flag      = 0;
    int s         = 4;

    while(low <= high){
        int index = low+(high-low)/2;
        if(array[index] == s){
            flag = 1;
            printf("Founded: %d \n",index);
            break;
        }
        else if(array[index] < s){
            low   = index+1;
        }
        else{
            high = index-1;
        }
    }
    if(flag == 0){
        printf("Not Found!\n");
    }

    return 0;
}