This article illustrates how to perform Binary Search using C Programming. Binary Search is the advancement of Linear Search. The main advantage of Binary Search is its Time Complexity is less than that of Linear Search.

In Binary Search C Program we will define 7 variables : `a[100]`

– an array, `n`

– used to fix the size of the array, `pos=-1`

– used to catch the value returned by the function and is initialized with -1, `key`

– used to read the input for searching a key, `j`

– used in for loop, `first`

– declared globally and is used in rbsearch function and is initialized with 0. `last`

– declared globally and is used in rbsearch function and is initialized with n-1.

`rbsearch`

function is used to perform the search operations. In Binary Search to trace out an element, depending on the condition `last>=first`

the element is traced. A variable `middle`

is declared inside rbsearch function in order to reduce the time complexity of Binary Search.

#include<stdio.h>
#include<conio.h>
int rbsearch(int[],int,int,int,int);
int first,last;
void main()
{
int a[100],n,pos=-1,key,j;
clrscr();
printf("Binary SEARCH\n");
printf("\nEnter array size : ");
scanf("%d",&n);
printf("\nEnter values into array : ");
for(j=0;j<n;j++)
scanf("%d",&a[j]);
printf("\nEnter the value to be serached : ");
scanf("%d",&key);
pos=rbsearch(a,key,n,0,n-1);
if(pos==-1)
printf("\nUnsuccessful");
else
{
printf("\nSuccessful");
printf("\nThe element %d is found at %d",key,pos+1);
}
getch();
}
int rbsearch(int a[],int key,int n,int first,int last)
{
int middle;
if(last>=first)
{
middle=(first+last)/2;
if(key<a[middle])
middle=rbsearch(a,key,n,first,middle-1);
else if(key>a[middle])
middle=rbsearch(a,key,n,middle+1,last);
else
return middle;
}
else
return -1;
}

Output:

*Related*

Tagged as:
C Programs

{ 0 comments… add one now }