Binary Search is a search algorithm that finds the position of a target value within a sorted array. Binary Search Algorithm compares the target value with middle element and then divides the array into subarrays.

It is based on Divide and Conquer Technique.

Worst Case Complexity : O(log n)

Average Case Complexity : O(log n)

Best Case Complexity : O(1) , when target value is present at middle position.

Code

#include<stdio.h>
int binarysearch(int array[],int size,int item)
{
 int beg,end,middle;
 beg=0;
 end=size-1;
 middle=(beg+end)/2;
 while(beg<=end) 
 {
 if(array[middle]<item)
 {
  beg=middle+1;    
 }
 else if(array[middle]==item) 
 {
  printf("%d found at location %d.\n",item, middle+1);
  break;
 }
 else
 {
  end=middle-1;
 }
 middle=(beg+end)/2;
 }
 if(beg>end)
 {
  printf("Not found!");
 }
}
int main()
{
 int array[100],item,i,size;
 printf("***** BINARY SEARCH BY CODE OF GEEKS *****\n\n");
 printf("ENTER THE SIZE OF AN ARRAY\n");
 scanf("%d", &size);
 printf("ENTER THE ARRAY : \n");
 for (i=0;i<size;i++)
 {
   scanf("%d", &array[i]);	
 }
 printf("ENTER A VALUE TO SEARCH\n");
 scanf("%d", &item);
 binarysearch(array,size,item);
 return 0;
}

Output

See this code in

C++ | Python | Java