Written by Sai Sandeep Thota on January 27, 2013 in C > Programming

C Program to implement Binary Search

GET ALERTS:

Get our Latest updates delivered to your mailbox!

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:
Binary-Search-C-Program

{ 0 comments… add one now }

Leave a Comment

Previous post:

Next post: