Binary Search

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();
}