In this article at OpenGenus, we have explained Binary search algorithm and implement a program on the same in C programming language using recursion.

Table of contents

• Problem statement
• How binary search works
• Time complexity
• Drawbacks of binary search
• Recursion in Binary Search
• Implementation of Binary Search in C using recursion
• Output
• Conclusion

Problem statement

In this article, we will learn binary search algorithm.

• Binary search algorithm is used to search an element in a given set of elements.
• It works on a sorted list of data.
• It starts searching from the middle index of the array and goes accordingly if the element is smaller or larger than the middle element.

How Binary search works

Following is how binary search works:

1. First the list of elements should be sorted.
2. Then we store the index of the first element in variable low and the index of the last element in variable high.
3. Now we store the index of the element which lies in the middle of the array in variable mid. We can find that index by (low+high)/2.
4. Next we compare the target element with mid, if it matches then we return index od mid.
5. If it doesn't match, then we compare if the target element is less than mid then it lies in the left side of the array or if it is greater than mid then it lies in the right side of the array.
6. Then again that half of the array where the element lies is divided into half and again step 4 and step 5 (if required) is repeated.

Example:

• Given array: {2,5,8,10,12,19,22}
• target element=19
• low=0, high=6
• mid=(low+high)/2
  =(0+6)/2=3
• {2,5,8,10,12,19,22}
  ...........^
  The element in index 3(mid) is 10 which is not equal to the target element 19. 19 is greater than the element in mid that is 10 which means that the element lies in the right side of the array as the array is sorted.
• Now low=mid+1
  =3+1
  =4
• mid=(low+high)/2
  =(4+6)/2
  =5
• {2,5,8,10,12,19,22}
  ....................^
  The element in index 5(mid) is 19 which is equal to the target element 19 so now we return mid.

Time complexity

• Best case time complexityof linear search is O(1) that is the element is present at middle index of the array.
• Worst case time complexity of linear search is O(logN), N being the number of elements in the array.

Drawbacks of Binary search

• Binary search works only on sorted data.

Recursion in Binary Search

The concept of recursion is to call the same function repeatedly within itself. There is a condition when this recursion stops.

At each step of Binary Search, we reduce the potential size of the array by half where the target element can be found.

Due to this, the function to search using binary search can apply the function recursively on a smaller part of the array. Due to this, the starting and ending index of the array can be defined in Binary Search function.

The pseudocode of Recursive Binary Search is:

binarySearch(int start_index, int end_index, int target_element) {
    mid = index of middle element
    Check if target_element is < middle element
        then potential array is the first half
    else
        check second half
    Accordingly, recursively call binarySearch on 
    first or second half
}

Implementation of Binary Search in C using recursion

• We define a function named binarySearch()
• It return an integer which is the index of the element to be searched.

Following is the implemention of the code in C programming language:

#include <stdio.h>
int binarySearch(int arr[], int low, int high, int x)
{
    if (high >= low) 
    {
        int mid = (low +high)/ 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, low, mid - 1, x);
        else
        return binarySearch(arr, mid + 1, high, x);
    }
    return 1;
}
 
int main(void)
{
    int arr[] = { 2,5,8,10,12,19,22 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int result = binarySearch(arr, 0, n - 1, x);
    if(result==1)
    	printf("Element is not present in array");
   	else
        printf("Element is present at index %d", result);
    return 0;
}

Output

Run the code as follows:

gcc code.c
./a.out

Following is the output of the program:

Element is present at index 5

Conclusion

Binary search is better than linear search when it comes to dealing with large datasets/arrays as the time complexity of linear search is O(N) whereas that of binary search is reduced to O(logN).

With this article at OpenGenus, you must have the complete idea of Binary Search in C using recursion.