Write a C Program to implement Binary Search using function

 Here we are going to write a c program to implement binary search using function. There are two popular searching techniques one is Linear Search and another is Binary Search. We have already discussed about Learn Search in C program to implement linear search post. Here we will discuss about Binary Search.

Binary Search works in the principle of Divide and Conquer rule. In this, we divide the array into two equal halves and compare the element which we are searching with the mid value if the element is less than the mid value in the array then we search for the element in one first half of the array and ignore the second half and vice versa. From here one exception we can see that Binary Search only works on already sorted array. So if we get an unsorted arrat then we first need to sort it before applying binary search on it. Now lets implement binary search in c. But before going down I will suggest you to first try it on your own and then see the solution.

C Program to implement Binary Search using function

#include <stdio.h>

void binarysearch(int a[], int n, int s)
{
    int beg = 0, end = n-1, flag = 0;
    int mid;
    while (beg <= end)
    {
        mid = (beg + end) / 2;
        if (s == a[mid])
        {
            printf("\nElement found at index %d", mid);
            flag = 1;
            break;
        }
        else if (s > a[mid])
        {
            beg = mid + 1;
        }
        else
        {
            end = mid - 1;
        }
    }
    if (flag == 0)
    {
        printf("\nElement not found!");
    }
}

int main()
{
    int n, i, j, temp, flag = 0;
    printf("Enter size of array: ");
    scanf("%d", &n);
    int a[n];
    printf("Enter array elements: ");
    for (i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (i = 0; i < n - 1; i++)
    {
        if (a[i] > a[i + 1])
        {
            flag = 1;
            break;
        }
    }
    
    if (flag == 1)
    {
        for (i = 0; i < n - 1; i++)
        {
            for (j = i + 1; j < n; j++)
            {
                if (a[i] > a[j])
                {
                    temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
        }
        printf("\nSorted Array: ");
        for (i = 0; i < n; i++)
        {
            printf("%d ",a[i]);
        }
    }
    int s;
    printf("\nEnter element to search: ");
    scanf("%d", &s);
    binarysearch(a, n, s);

    return 0;
}

Output

Enter size of array: 5
Enter array elements: 2 3 1 4 5

Sorted Array: 1 2 3 4 5  
Enter element to search: 4

Element found at index 3

Time complexity - 

• Best Case - O(1)

• Average Case - O(logn)

• Worst Case - O(logn)

Best case is when there is only one element in an array.

More like this

• Program to implement Linear Search

• Program to implement Linear Search Using function