Searching and Sorting 569
printf("
The number of iterations are: %d",j);
}
else printf("n Number Is not found ■);
getchO ;
}
OUTPUT:
Enter the array elements: 12 5 8 7
Enter the number from the list for searching: 5
The position of element 5 is: 3
The number of iterations are: 3
Explanation In the above program an array of five elements is declared. Numbers are entered
and stored in the array. The number whose position is to be located is entered from the keyboard.
The entire array is scanned and the given number is checked with all the elements one by one.
When the element is found, the
break statement terminates the loop. The number of iterations
and location of the element in the array are always same. This is because, as soon as an element is
found loop is terminated. The array elements are accessed according to the iterations of the loop.
The ' if' statement checks the value of j, and if it is less than five, the position and number of
iterations are displayed else message "Number is not found" is displayed.
16.4 BINARY SEARCH
Binary search offers comparatively lesser number of iterations than the linear search.
In this method, the elements are not searched sequentially like linear search. Instead of this, two
compartments of the list are done. Each compartment will be having an equal number of items.
The lower compartment contains approximately half the elements and this compartment is called
lower half. The upper compartment containing upper elements is upper half. Then the given element
is searched. The element may be found in the lower half or the upper half of the compartments. It
creates two parts of the lists hence it is known as binary search.
Binary search is quicker than the linear search. However, it cannot be applied on unsorted data
structure. Before applying binary search, the linear data structure must be sorted in either ascending
or descending order. The binary search is based on the approach divide-and-conquer. In this method,
the element to be searched is compared with the middle element. If the match is observed then the
element is successfully searched. Otherwise the element is compared with the items of the two
compartments, that is, it is compared with the items falling under the lower half or upper half
compartments. If the expected item is less than the middle element, the lower half compartment is
search. If it is larger than the middle, upper half compartment ^s searched. These steps are illustrated
in Fig. 16.3.
570 Programming and Data Structures
Fig. 16.3 Binary search
16.2 Write a program to sort an array elements using binary search.
#±nclude <stdio.h>
#include <conio.h>
main()
{
in t items [2 0 ], s « 0 , e , n , j , num,mid;
c l r s c r ( ) ;
p rin t f ( an Enter number of elements: ■ );
scanf (*%d",&n);
fo r (j«0 ;j< n ;j+ + )
{
p rin tf (" Enter element %d: " ,1 + j);
scanf (■%d"/&iterns[j]);
}
p rin tf ( ”
Enter element to be searched:”);
scanf ( ”%d", &num);
•■n-1;
m id«(s+e)/2 ;
while (num!sitems[mid] && e<*e)
{
Searching and Sorting 571
i f (num>iterns [mid] ) e«m id-l;
else s=mid+l;
m id=(s+e)/2;
}
i f (numssiterns [mid] )
p r in tf ("n %d found at position %d " , num,++mid);
i f (s>e) p rin tf (" %d not found ", num);
getchO ;
}
OUTPUT:
Enter number of elements: 7
Enter element 1: 7
Enter element 2: 3
Enter element 3: 2
Enter element 4:1
Enter element 5: 5
Enter element 6: 4
Enter element 7: 7
Enter element to be searched: 7
7 found at position 1
Explanation In the above program an array ite m s [2 0] elements is declared. The user is
prompted to enter num ber of elements to be in the list. The numbers are entered through the
keyboard. The variable s keeps track of the starting of the list and the variable e keeps track of the
end. The middle is calculated with the formula m id=(s+e)/2; If the sum of (s+e) is odd number then
the result of division operation w ould be a f l o a t value. However, all the operands (s,e) of equation
are integers, the flo a t value is converted to lowest integer.
16.3 Write a program to demonstrate binary search. Use character array and store 10 names.
#in clu de <stdio .h>
#in c lu de <strin g.h>
#include<conio.h>
main()
{
in t beg=l,m id,end-10, i , fla g = 0 , v a l ;
char name[1 5 ][1 0 ],f n [15 ];
c l r s c r ( ) ;
p r i n t f ( "Enter 10 names: - n");
572 Programming and Data Structures
f o r ( i « l ; i < l l ; i + + )
sca n f("% s", fcname[i]) ;
p r i n t f ("ntEnter the name to s e a rc h :");
sc a n f( ”%s”, & fn );
mid* (beg-fend) /2;
p rin t f ("ntAt sta rtin g beg is %d, mid is %d & end is %dn,beg/mid, end) ;
w h ile ( (strcmp(fn,name[mid]))1=0 && beg<=end)
{
valastrcm p(fn,name[m id]) ;
if(v a l> 0 )
{
beg»mid+l;
mi d«(beg+end)/2;
p r i n t f ("ntmid is %d & beg is % d",m id,beg);
}
else
{
end«m id-l;
mid*(beg+end)/2;
p r i n t f ("ntmid is %d & end is %d",mid,end);
}
}
if(strcm p(fn,n am e[m id ])= * 0 ){ f l a g » l ; }
i f ( f l a g » - l )
p r i n t f ("ntThe name %s is traced s u c c e ss fu lly ", f n ) ;
else
p r in t f ("ntThe number %s is not tr a c e d ",fn );
getche( ) ;
}
OUTPUT;
Enter 10 names:
ashish bhaskar deepak dinesh gajanan ganesh gopal govind raj ramash
Enter the name to search:deepak
At starting beg is 1, mid is 5 & end is 10
mid is 2 & end is 4
mid is 3 & beg is 3
The name deepak is traced successfully
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.