.PNG)
Program Statement :
Write a C program to find a particular element from an array using binary search method.
Theory :
Searching is an operation which finds the location of a given element in a list. The search is said to be successful or unsuccessful depending on whether the element that is to be searched is found or not.
Binary search method is very fast and efficient. This method requires that the list of elements be in sorted order. In this method, to search an element we compare it with the element present at the center of the list. If it matches the search is successful. Otherwise the list divided into two halves :-
1. One from 0th element to the center element (whose elements are smaller than the center element).
2. Another one is from center element to the last element (whose elements are greater than the center element).
Now if the searching element is smaller than the center element then searching will be done in the first half, otherwise in the second half.
This procedure is repeated till the element is found or division of half parts gives one element.
Suppose an array consists of 10 elements and 52 is the element that is to be searched.
It works as follows:-
Algorithm :
/* Lower bound and upper bound of the input array, searching element and the input array are passed as parameters */
Algo_bsrch(lb, ub,key, arr[])
{
while(lb<=ub)
{
mid_index = (lb+ub)/2;
If(key = arr[mid_index]) /* Searching element is at the mid-index */
Return mid_index;
Else If(key<arr[mid_index])
ub = mid_index-1;
Else
lb = mid_index+1;
}
Return False; /* Search is unsucessful */
}
/* End of Algo_bsrch */
Program listing :
/* C program to find a particular element from an array of elements using binary search method */
#include<stdio.h>
#define max 50 /*Defining maximum size of the array*/
void main()
{
int i,j,n,mid_index,a[max],lb,ub,s;
int bsrch(int,int,int,int[]);
printf("Give number of elements in the array : ");
scanf("%d",&n);
printf("nEnter the elements in ascending order : ");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
if(i!=0 && a[i]<a[i-1])
{
printf("!!!!!Invalid input!!!!!n");
printf("Enter an element greater than %dn",a[i-1]);
i--;
}
}
printf("nThe sorted array(in ascending order)is : ");
for(i=0;i<n;i++)
printf("%4dn",a[i]);
lb=0; /*Defining lower bound of the array*/
ub=n-1; /*Defining upper bound of the array*/
printf("nGive the value to search for : ");
scanf("%d",&s); /*Read the element to search from user*/
if((i=bsrch(lb,ub,s,a))==-1)
printf("nSearch unsuccessful.n");
else
printf("Search successful.nValue found at position : %dn",i+1); /*Search is successful and position where the element is found is printed*/
}
/*Lower bound and upper bound of the input array ,searching element and the input array are passed as parameters*/
int bsrch(int lb,int ub,int s,int a[]) /*function for binary search.
{
int mid_index;
while(lb<=ub)
{
mid_index=(lb+ub)/2;
/*Searching element is at the mid-index*/
if(s==a[mid_index])
return mid_index;
else if(s<a[mid_index])
ub=mid_index-1;
else
lb=mid_index+1;
}
return -1; /*Search is unsucessful*/
}
Output :
SET 1 :
Give number of elements in the array : 10
Enter the elements in ascending order : 12 31 33 41 55 67 72 91 112 158
The sorted array(in ascending order)is :
12
31
33
41
55
67
72
91
112
158
Give the value to search for : 91
Search successful.
Value found at position : 8
SET 2 :
Give number of elements in the array : 8
Enter the elements in ascending order : 15 21 55 61 77 81 97 118
The sorted array(in ascending order)is :
15
21
55
61
77
81
97
118
Give the value to search for : 41
Search unsuccessful.
Discussions :
● COMPLEXCITY OF BINARY SEARCH :
In the best possible case, the ITEM may occur at middle position. In this case, the search operation terminates in success with just one comparison.
After each comparison either the search terminates successfully or the size of the array remaining to be searched is about one half of the original size. So after j comparisons the array remaining to be examined is of size at most N/2j . In the worst case the search terminates when there are only one element remaining to be searched. Hence,
N/2j = 1
Or, N = 2j
Or, N = log2N
Thus in worst case, this method requires O(log2N) comparisons to search an element in the array. The maximum number of comparisons in binary search is limited to log n.
● ADVANTAGE :
The advantage of binary search method is that, in each iteration it reduces the number of elements to be searched from n to n/2. On the other hand, linear search method checks sequentially for every element, which makes it inefficient.
● DISADVANTAGE :
The disadvantage of binary search is that it works only on sorted lists. So when searching is to be performed on unsorted list then linear search is the only option.
● Alternatively if user input is an unsorted list then it can be made sorted by using any sorting method and after that we can imply binary search method on the list. But it is not feasible as complexity of the program will become much higher.
Write a C program to find a particular element from an array using binary search method.
Theory :
Searching is an operation which finds the location of a given element in a list. The search is said to be successful or unsuccessful depending on whether the element that is to be searched is found or not.
Binary search method is very fast and efficient. This method requires that the list of elements be in sorted order. In this method, to search an element we compare it with the element present at the center of the list. If it matches the search is successful. Otherwise the list divided into two halves :-
1. One from 0th element to the center element (whose elements are smaller than the center element).
2. Another one is from center element to the last element (whose elements are greater than the center element).
Now if the searching element is smaller than the center element then searching will be done in the first half, otherwise in the second half.
This procedure is repeated till the element is found or division of half parts gives one element.
Suppose an array consists of 10 elements and 52 is the element that is to be searched.
It works as follows:-
/* Lower bound and upper bound of the input array, searching element and the input array are passed as parameters */
Algo_bsrch(lb, ub,key, arr[])
{
while(lb<=ub)
{
mid_index = (lb+ub)/2;
If(key = arr[mid_index]) /* Searching element is at the mid-index */
Return mid_index;
Else If(key<arr[mid_index])
ub = mid_index-1;
Else
lb = mid_index+1;
}
Return False; /* Search is unsucessful */
}
/* End of Algo_bsrch */
Program listing :
/* C program to find a particular element from an array of elements using binary search method */
#include<stdio.h>
#define max 50 /*Defining maximum size of the array*/
void main()
{
int i,j,n,mid_index,a[max],lb,ub,s;
int bsrch(int,int,int,int[]);
printf("Give number of elements in the array : ");
scanf("%d",&n);
printf("nEnter the elements in ascending order : ");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
if(i!=0 && a[i]<a[i-1])
{
printf("!!!!!Invalid input!!!!!n");
printf("Enter an element greater than %dn",a[i-1]);
i--;
}
}
printf("nThe sorted array(in ascending order)is : ");
for(i=0;i<n;i++)
printf("%4dn",a[i]);
lb=0; /*Defining lower bound of the array*/
ub=n-1; /*Defining upper bound of the array*/
printf("nGive the value to search for : ");
scanf("%d",&s); /*Read the element to search from user*/
if((i=bsrch(lb,ub,s,a))==-1)
printf("nSearch unsuccessful.n");
else
printf("Search successful.nValue found at position : %dn",i+1); /*Search is successful and position where the element is found is printed*/
}
/*Lower bound and upper bound of the input array ,searching element and the input array are passed as parameters*/
int bsrch(int lb,int ub,int s,int a[]) /*function for binary search.
{
int mid_index;
while(lb<=ub)
{
mid_index=(lb+ub)/2;
/*Searching element is at the mid-index*/
if(s==a[mid_index])
return mid_index;
else if(s<a[mid_index])
ub=mid_index-1;
else
lb=mid_index+1;
}
return -1; /*Search is unsucessful*/
}
Output :
SET 1 :
Give number of elements in the array : 10
Enter the elements in ascending order : 12 31 33 41 55 67 72 91 112 158
The sorted array(in ascending order)is :
12
31
33
41
55
67
72
91
112
158
Give the value to search for : 91
Search successful.
Value found at position : 8
SET 2 :
Give number of elements in the array : 8
Enter the elements in ascending order : 15 21 55 61 77 81 97 118
The sorted array(in ascending order)is :
15
21
55
61
77
81
97
118
Give the value to search for : 41
Search unsuccessful.
Discussions :
● COMPLEXCITY OF BINARY SEARCH :
In the best possible case, the ITEM may occur at middle position. In this case, the search operation terminates in success with just one comparison.
After each comparison either the search terminates successfully or the size of the array remaining to be searched is about one half of the original size. So after j comparisons the array remaining to be examined is of size at most N/2j . In the worst case the search terminates when there are only one element remaining to be searched. Hence,
N/2j = 1
Or, N = 2j
Or, N = log2N
Thus in worst case, this method requires O(log2N) comparisons to search an element in the array. The maximum number of comparisons in binary search is limited to log n.
● ADVANTAGE :
The advantage of binary search method is that, in each iteration it reduces the number of elements to be searched from n to n/2. On the other hand, linear search method checks sequentially for every element, which makes it inefficient.
● DISADVANTAGE :
The disadvantage of binary search is that it works only on sorted lists. So when searching is to be performed on unsorted list then linear search is the only option.
● Alternatively if user input is an unsorted list then it can be made sorted by using any sorting method and after that we can imply binary search method on the list. But it is not feasible as complexity of the program will become much higher.
