Binary Search Algorithm in C

This is a C Program to search an element in an Array using Binary Search Algorithm using recursion.

Problem Description

We have to create a C Program which inputs a sorted array and tells whether the key searched is present in array or not using Binary Search Algorithm recursively. We have to take array and the key as an input from the user.

Expected Input and Output

1. Average Case: When the element to be searched is other than the middle element.
For example:

If the input array is {1, 2, 3, 4, 5, 6}
and the key to be searched for is 6
then the expected output will be "Search Successful".

Average case time complexity: O(log n).

2. Best Case: If the element which is searched is the middle element of the array.
For example:

If the input array is {1, 5, 9}
and the key to be searched is 5,
then the expected output will be "Search Successful".

Best case time complexity: O(1).

3. Worst Case: If the element to be searched for is not present in the array.
For example:

Note: Join free Sanfoundry classes at Telegram or Youtube

If the input array is {1, 3, 6, 8, 9}
and the key to be searched for is 4,
then the expected output will be "Search Unsuccessful".

Worst case time complexity: O(log n).

Problem Solution

1. We will be having an array of numbers, we just need to find out the whether the element is present in an array or not.
2. It can be done using Binary Search by recursion or iteration methods. Here in this problem we will do it using recursion.
3. The basic idea behind Binary Search is that the array in which it is applied upon should be sorted. It divides the whole array into two halves and proceeds to look for the key in suitable part of divided array.

Program/Source Code

Here is source code of the C Program to perform Binary Search using recursion. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on Windows 10. The program output is also shown below.

```
/*
```

 * C Program to Perform Binary Search using Recursion

```
 */
```
```
 
```
```
#include <stdio.h>
```
```
 
```

void binary_search(int [], int, int, int);

```
void bubble_sort(int [], int);
```
```
 
```
```
int main()
```
```
{
```
```
    int key, size, i;
```
```
    int list[25];
```
```
 
```
```
    printf("Enter size of a list: ");
```
```
    scanf("%d", &size);
```
```
    printf("Enter elements\n");
```
```
    for(i = 0; i < size; i++)
```
```
    {
```
```
        scanf("%d",&list[i]);
```
```
    }
```
```
    bubble_sort(list, size);
```
```
    printf("\n");
```
```
    printf("Enter key to search\n");
```
```
    scanf("%d", &key);
```
```
    binary_search(list, 0, size, key);
```
```
 
```
```
}
```
```
 
```
```
void bubble_sort(int list[], int size)
```
```
{
```
```
    int temp, i, j;
```
```
    for (i = 0; i < size; i++)
```
```
    {
```
```
        for (j = i; j < size; j++)
```
```
        {
```
```
            if (list[i] > list[j])
```
```
            {
```
```
                temp = list[i];
```
```
                list[i] = list[j];
```
```
                list[j] = temp;
```
```
            }
```
```
        }
```
```
    }
```
```
}
```
```
 
```

void binary_search(int list[], int lo, int hi, int key)

```
{
```
```
    int mid;
```
```
 
```
```
    if (lo > hi)
```
```
    {
```
```
        printf("Key not found\n");
```
```
        return;
```
```
    }
```
```
    mid = (lo + hi) / 2;
```
```
    if (list[mid] == key)
```
```
    {
```
```
        printf("Key found\n");
```
```
    }
```
```
    else if (list[mid] > key)
```
```
    {
```

        binary_search(list, lo, mid - 1, key);

```
    }
```
```
    else if (list[mid] < key)
```
```
    {
```

        binary_search(list, mid + 1, hi, key);

```
    }
```
```
}
```

Program Explanation

1. A Binary Search is a quick and efficient method of finding a specific target value from a set of ordered items. A Binary Search, also known as a half-interval search.
2. In Binary Search the key value which is to be searched is compared to the middle element of the array. If the key value is less than or greater than this middle element, the algorithm knows which half of the array to continue searching in because the array is sorted.
3. This process is repeated until we discover the element. In each step this algorithm divides the array size by half and the Binary search will be successful if it is able to locate the element in array, but if it cannot find the element in array it simply returns -1 or prints “Key not Found”.
4. Worst case time complexity of Binary Search it is O(log n). The Best case time complexity of Binary Search is O(1). The only condition for implementing Binary Search is that the array should be sorted.

Runtime Test Cases

1. Enter size of a list: 6
   Enter elements
   1
   2
   3
   4
   5
   6
 
   Enter key to search
   6
   Key found
 
2. Enter size of a list: 3
   Enter elements
   1
   5
   9
 
   Enter key to search
   5
   Key found
 
3. Enter size of a list: 5
   Enter elements
   1
   3
   6
   8
   9
 
   Enter key to search
   4
   Key not found

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at other example programs on Searching and Sorting, go to C Programming Examples on Searching and Sorting. If you wish to look at programming examples on all topics, go to C Programming Examples.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Implement Merge Sort Algorithm

» Next - C Program to Implement Selection Sort using Recursion

Related Posts:

Recommended Articles: