Accept n sorted values in array from user. Accept a value x from user and use binary search algorithm to check whether the number is present in sorted array or not and output the position if the number is present.

BINARY SEARCH :

Binary Search is used with sorted array or list. So a necessary condition for Binary search to work is that the list/array should be sorted. It works by repeatedly dividing in half the portion of the list that could contain the item. 

Algorithm:

Step 1: Start 

Step 2: Accept n numbers in an array num and a number to be searched 

Step 3: set low=0, high=n-1 and flag=0 

Step 5: if low <= high then middle=(low+high)/2 else goto step 8. 

Step 6: if (num[middle]=number) position=middle, flag=1 goto step 8. else if (number< num[middle]) high=middle-1 else low=middle+1 

Step 7: goto step 5 

Step 8: if flag=1 Print “Required number is found at location position+1” Else Print “Required number is not found.

 Step 9: Stop 

Time Complexity:

 Base Case: O(1)

 Worst Case: O(log n)

Average Case: O(log n)

PROGRAM :

#include<stdio.h>
#define max 10

int main()
{
int a[max],i,n,key,high,low=0,mid;

printf("how many array elements:");
scanf("%d",&n);
printf("Enter array:");
accept(a,n);//calling function

printf("Array elements are:\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);//displaying array

printf("\nEnter number to search:");
scanf("%d",&key);
binarysearch(0,n-1,a,key);//calling function
}

//function binary
void binarysearch(int low,int high,int a[],int key)
{
 int mid;
 if(low>high)
 {
  printf("Search is not successful\n");
  return;
 }
 mid=(low+high)/2;
 if(key==a[mid])
 {
  printf("Search Found at index %d\n",mid+1);
  return;
 }

 else if(key<a[mid])
 {
  return binarysearch(low,mid-1,a,key);
 }
 else if(key>a[mid])
 {
  return binarysearch(mid+1,high,a,key);
 }
}
//Accept function to store element
void accept(int a[],int n)
{
int i;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
}

OUTPUT  :

how many array elements:5
Enter array:1 2 3 4 5
Array elements are:
1 2 3 4 5
Enter number to search:4
Search Found at index 4

Process returned 0 (0x0)   execution time : 7.793 s
Press any key to continue.