Binary search implememtation in C Language

In previous post we have seen how we can search the list by using simple loop and process is called sequential search. This is useful when we have small lists. But in real world we encounter large lists having thousands or even millions of elements(data).

Iterating over such a large list using simple loop is inefficient in terms of time. Considering the large list having sorted elements we can employ binary search. Generally when storing the data itself if we stored them in sorted order makes our life simple at later part of time when we are retrieving data.

If you observe the name of search algorithm "Binary Search". It conveys we have two parts(Binary). The part of the list having the desired data and the part does not having the desired data.

The c code which explains the binary search is as follows:

int binarySearch(int* array, int size, int reqNum, bool *result )
{
    int startIdx;
    int endIdx;
    int midIdx;
   
    startIdx = 0;
    endIdx = size;
   
    while ( startIdx <= endIdx)
    {
        midIdx = ( startIdx + endIdx ) / 2 ;
        if (reqNum > array[midIdx])
        {
            startIdx = midIdx + 1;
        }
        else if (reqNum < array[midIdx])
        {
            endIdx = midIdx - 1;
        }
        else
        {
            startIdx = endIdx + 1;
        }
    }
    *result = ( reqNum == array[midIdx]);
    return midIdx+1;
}

The logic returns the position of the desired elements in the list. But if we dose not have the required data in the list then also the algorithm returns the 1. but before that we are comparing if the required number is present at the array[midIdx] if the number does not there we are passing the failure as the pointer to the calling function. By using that the calling function can determine weather the data is present in the list are not.

the calling function can be coded as

int main ()
{
    int a[10] = {1,2,120, 240, 256, 300,312, 440, 456, 512};
    bool result;
    int index = binarySearch(a,10, 0, &result );
    if (result)
    {
        printf("Required Number Present at %d position",index );
    }
    else
    {
        printf("Target not found");
    }
}