C program for Binary Search

Binary Search:- It is a method used to search an element present in an array. It can be implemented only on the sorted array. If you want to search an element using binary search you need to sort the array either in increasing order or decreasing order. Once the array is sorted you can implement binary search algorithm to find the position of  the desired element. It's very fast as compared to linear search. You can use any sorting algorithm before implementing binary search algorithm.

It may also called half-interval search or logarithmic search.

Algorithm:-

Given an array 'array' of 'n' elements with values or records arry₀ ... array_n−1, sorted such that array₀ ≤ ... ≤ array_n−1, and target value 'search', the following subroutine uses binary search to find the index of 'search' in 'array'.

1. Set 'first' to 0 and 'last' to n − 1.
2. If  first> last, the search terminates as unsuccessful.
3. Set 'mid' (the position of the middle element) to the floor of (first + last) / 2.
4. If array_m < search, set first to mid + 1 and go to step 2.
5. If array_m > search, set last to mid – 1 and go to step 2.
6. Now array_m = search, the search is done; return mid.

Here, we tried to search '76' using binary search :- 

Complexities of Binary Search :-

Worst case performance	O(log n)
Best case performance	O(1)
Average case performance	O(log n)
Worst case space complexity	O(1)

Here the code below assumes that the input numbers are in ascending order.

C Programming code for Binary Search:-

#include<stdio.h>
int main()
{
   int i,first,last,middle,n,search,array[100];
   printf("----------Enter number of elements----------\n");
   scanf("%d",&n);
   printf("----------Enter %d integers----------\n", n);
   for (i=0;i<n;i++)
      scanf("%d",&array[i]);
   printf("----------Enter the element to search----------\n");
   scanf("%d",&search);
   first=0;
   last=n-1;
   middle=(first+last)/2;
   while (first<=last)
{
      if(array[middle]<search)
         first=middle+1;
      else if(array[middle]==search)
      {
         printf("%d found at location %d.\n", search,middle+1);
         break;
      }
      else
         last=middle-1;
      middle=(first+last)/2;
   }
   if(first>last)
      printf("Element Not found! %d is not present in the list.\n",search);
   return 0;
}

Output of the above Binary Search programme:-