Binary Search

Monday, August 15th, 2011

A binary search program locates the position of an item in a sorted array.

Logic: The Binary search starts by testing the element at the middle of the array. Let us consider an array ‘a’ with all elements arranged in ascending order. Let low and high are the lower and upper indices of the array ‘a’, respectively. We want to search an item K in it. To do this, we calculate a middle index with the values of low and high, let it be mid. Then we compare if K=a[mid] or not.

If it is true, then search is done. Otherwise, the search is to be repeated on left or right half depending on the K<a[mid] or K>a[mid], respectively. In case of low =high and K a[mid], the search terminates unsuccessfully.

Example 1:

Consider the following elements stored in an array,

Example 2:

Consider the following elements stored in an array,

Program:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include"stdio.h"
#include"conio.h"
void main()
{
	int a[25], i, n, K, flag = 0, low, high, mid;
	clrscr();
	printf("Enter the number of elementsn");
	scanf("%d", &n);
	printf("Enter the elementsn");
	for(i = 0; i<n; i++)
	{
		scanf("%d",&a[i]);
	}
	printf("Enter the key to be searchedn");
	scanf("%d",&K);
	low = 0;
	high = n - 1;
	while(low <= high)
	{
		mid = (low+high)/2;
		if(a[mid] == K)
		{
			flag = 1;
			break;
		}
		else if(K<a[mid])
			high = mid-1;
		else
			low = mid + 1;
	}
	if(flag == 1)
	{
		printf("Key element is found");
	}
	else
	{
		printf("Key element not found");
	}
	getch();
}

Author Name :
chitra

Total : 2 Comments


2 Responses to “Binary Search”

  1. nima askarian omran says:

    hi
    thanks

  2. Mukesh Rajput says:

    This tutorial is nice. Thanks.

Leave a Reply

Question and Answer
C/C++ Unix & Linux Wordpress
Source codes
C C++ Java

Free email signup

Email: