Facebook

Binary Search

Binary Search

The binary search technique works only on sorted array.It works by comparing the input element to the middle element of array.The comparison determines whether the element is less than.greater than or equal to middle element.Subsequent steps to be followed are written and explained by the following program.

Program

#include <stdio.h>

int main()
{
	int val[10] = {10,20,30,40,50,55,68,77,89,90};//Fig 3
	int beg = 0;   //first index of array
	int end = 9;  //end(last index of array)  = n-1 where n is the size of array and is 10 in this case.
	int mid = (beg+end)/2; // finds middle index of array.
	int i;
	int element;
	//printf("enter the element you want search for");
	scanf("%d",&element);
	for(i=0;i<10;i++) //Fig 4
	{
	if(val[mid] == element)	{
		break;
	}
	else if(val[mid] < element) {
	beg = mid +1;
	mid = (beg +end)/2;
	}
	else{
	end =mid -1;
		mid = (beg +end)/2;
	}
	}
	printf("Location of element is %d",mid);
	return 0;
}

Run

Illustration
Fig 3:An Array
Fig 3:An Array
  • val[10] of int type is initialized with values 10,20,30,40,50,55,68,77,89,90.
  • beg variable of int type denotes the first index of array i.e. 0
  • end variable of int type denotes the last index of array .It is equal to (n-1),where n is the size of array.Here it is 10 so end=10-1=9
  • mid index is calculated by adding beg plus end and the dividing the result by 2.
  • element variable of int type is the data item which needs to be searched for in array and is entered by user using scanf.
  • Say we want to search for 68 .
  • The following ¬†figure explains the working of for loop to find 68.
Screen Shot 2014-03-19 at 4.43.35 PM
Fig 4 : Explanation of Binary Search Program
Rate this post

Comments

This post currently has one response

Leave a Reply

Your email address will not be published. Required fields are marked *

Sidebar