Binary Search in C

By | August 1, 2019

Binary search is a searching algorithm, used to tell the position of a value that is stored in an array. It is called a binary search because in order to search the value it divides the array into 2 parts.

What is Binary Searching?

It is a searching algorithm that can only be applied on a sorted array.

In binary search we first find the middle element of the array by dividing it into two parts (lower half array and upper half array) then compare it with our target element, if the target element is equal to the middle element of array, we return the element position plus one because elements store in array use indexing which starts from 0.

If the target element is smaller than middle element then we again divide the lower half array into two parts and compare the middle element with the target element, we will continue to do this process until the middle element, found equal to the target element.

If the target element is larger than middle element then we again divide the upper half array into two parts and compare the middle element with the target element, we will continue to do this process until the middle element, found equal to the target element

In programming, we can perform the repetitive action by using two tools which are iteration and recursion. In iteration, we use loops such as for, while and do-while and in recursion, we use recursion function.

Binary Search Time Complexity:

Best Case:

O(1)

Worst Case:

O(log n)

Advantages of Binary Search:

  • It uses the divide and conquers technique
  • It is faster than a linear search
  • Already present in the many libraries
  • Easy to implement

Disadvantages of Binary search

  • It works only on a sorted array

Binary Search in C

Here we have provided a binary search program in C using iterators and Recursion:

C iterative Binary Search:

In Iterative Binary search we will use while loop.

#include <stdio.h>
#include<conio.h>
int main()
{
   int i, f, l, mid, num, tar, arr[100];
   clrscr();
   printf("How many numbers you want to enter in the array: ");
   scanf("%d",&num);
   printf("Please Enter Elements in Ascending order\n");
   for (i = 0; i < num; i++)
      scanf("%d",&arr[i]);
   printf("Enter the number which position you want to know: ");
   scanf("%d", &tar);
   f = 0;
   l = num - 1;
   mid = (f+l)/2;
   while (f <= l) {
      if (arr[mid] < tar)
                 f = mid + 1;
      else if (arr[mid] == tar) {
                 printf("%d is at %d position\n", tar, mid+1);
          break;
      }
      else
             l = mid - 1;
      mid = (f + l)/2;
   }
   if (f> l)
      printf("This element is not in the Array");
getch();
}

Output:

How many numbers you want to enter in the array: 6
Please Enter Elements in Ascending order

12
23
34
45
56
67

Enter the number which position you want to know: 23

23 is at 2 position

C Recursive binary Search:

In Recursive binary search, we will use the recursion of function.

#include <stdio.h>
#include<conio.h>
int BinarySearch(int arr[], int l, int r, int tar)
{
    int mid;
    if (r >= l) {
                mid = l + (r - l) / 2;
                if (arr[mid] == tar)
                    return mid;
    if (arr[mid] > tar)
                return BinarySearch(arr, l, mid - 1, tar)
    return BinarySearch(arr, mid + 1, r, tar);
    }
    return -1;
}
void main()
{
    int arr[100],i,res,num,tar;
    clrscr();
    printf("How many Elements you wan to enter in the array: ");
    scanf("%d",&num);
    printf("Enter Elements in the Ascending order\n");
    for(i=0;i<num;i++)
         scanf("%d",&arr[i]);
   printf("Enter the element which position you want to know: ");
   scanf("%d",&tar);
   res = BinarySearch(arr, 0, num - 1, tar);
   if(res == -1)
       printf("The element is not present in array");
   else
       printf("%d is at %d position", tar,res+1);
getch();
}

Output:

How many Elements you want to enter in the array: 5
Enter Elements in Ascending order

12
224
35
46
68

Enter the element which position you want to know: 46

46 is at 4 position

People Also Read:

Leave a Reply

Your email address will not be published. Required fields are marked *