C Program to Search for an Element in an Array Using Binary Search


There is a condition for performing binary search, the prerequisite for binary search is that the array should be sorted. Firstly we compare the item to be search with the middle element of the array, if the the item is found the search is successful otherwise the array is divided into two halves, first half contains all the elements to the left of the middle element and the other one consists of all the elements to the right side of the middle element. Since the array is sorted, all the element in the left half will be smaller than the middle element and greater than the middle element in the right half. If the item to be search is less than the middle element, it will be search in left half otherwise it will be search in the right half (if it is greater then the middle element). Let’s now see the c program to search for an element in an array using binary search.

C Program ►►

#include<stdio.h>
#include<conio.h>

//Function Prototype Declaration
int binarySearch(int [],int,int);
 
void main()
{
   int size,arr[100],item,index;

   printf("Enter the Size of the Array : ");
   scanf("%d",&size);

   printf("\nEnter the elements of the Array : ");
   
   for(int i=0;i<size;i++) {
   printf("\nArray[%d] = ",i+1);
   scanf("%d",&arr[i]);
   }

   printf("\nEnter the Item to be searched : ");
   scanf("%d",&item);

   index=binarySearch(arr,size,item); //Function Call

   if(index==-1)
   printf("\n%d not found in the Array... Existing...",item);

   else
   printf("\n%d found at position %d ",item,++index);
 
   getch();   
}

 //Function Definition
int binarySearch(int arr[],int size,int item)
{
int low=0,up=(size-1),mid;

while( low<=up ) {

mid=(low+up)/2;

   if(item<arr[mid])
      up=mid-1;     // Search in left half

   elseif(item>arr[mid])
      low=mid+1;    // Search in right half

   else
      return mid;
    }
return -1;
}

Explanation ►► To implement this procedure we declared 3 variables viz. low,up and mid that will keep track of lower limit, upper limit, and middle value of that portion of the array, in which we will search for the element. The middle element of the array would be arr[mid].

The item is first compared with the middle element of the array following by if(item<arr[mid]), if it is smaller then we need to search in the left half of the array that is why we update the value of the up variable to be mid-1 to search in the left half, and if the element is larger by the value of the arr[mid] element than we need to search in right half for that we updated the value of low variable to be mid+1 to search in the right half of the array.

NOTE : The binary search can only be apply if the array is sorted otherwise it will not work. So if your array is not sorted, make it sorted first using any sorting technique.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s