5.linear search & binary search

PROGRAM - V

(A) Problem Statement :

Write a program to search for a particular string
from given set of strings using linear search and binary search
techniques.

(B) Input and Output :

This program takes the set of strings and string to be
searched and technique used search the string in the given set
of strings.


(i) Enter string: balaji
Do you want to enter another string (y/n) y
Enter string: Jaya
Do you want to enter another string (y/n) y
Enter string: Vignesh
Do you want to enter another string (y/n) y
Enter string: Chanthi
Do you want to enter another string (y/n) n

balaji
Jaya
Vignesh
Chanthi

1. Linear search 2. Binary search

Enter the technique: 1
Enter the string to be searched: Vignesh
The string Vignesh is present at position 3 in list.



(ii) Enter string: balaji
Do you want to enter another string (y/n) y
Enter string: Jaya
Do you want to enter another string (y/n) y
Enter string: Vignesh
Do you want to enter another string (y/n) y
Enter string: Chanthi
Do you want to enter another string (y/n) n


balaji
Jaya
Vignesh
Chanthi


1.linear search 2. binary search

Enter the technique : 2
Enter the string to be searched : Vignesh

Sorted list of strings is
balaji
Chanthi
Jaya
Vignesh

The string vigneshis found at position 4 in sorted list.


(C) Examples :

(i) the list is { balaji,Jaya,Vignesh,Chanthi}
String to be searched (str): jaya
S: balaji,Jaya,Vignesh,Chanthi
0 1 2 3
Compare s[0] with str it is not equal
Compare s[1] with str it is equal.
The string jaya is at (1+1) 2nd position in the list.

(ii) the list which is sorted is { balaji, Chanthi, Vignesh }
String to be searched (str) :balaji
S: aruna, chinni, vidula
0 1 2
Mid = (start + end)/2 = (0+2)/2 = 1
Compare s[mid] and str.not equal and s[mid] Start = start = 0 and end = mid-1 = 1-1 =0
Mid = (start+end)/2 = 0
S[mid] = str element is found
The string is found at (0+1) position.



(D)Algorithm :

Step 1: Start
Step 2: Read the list of strings
Step 3: Read the technique used for search and
string to be searched.
Step 4: If the technique is
(a) linear search
(i) repeat the following steps (ii) and (iii)
from I value 0 to length of list- 1.
(ii) compare given string with I th string
in the list.
(iii) if string is found then print the
position of string in the list and exit.
(iv) if string not found print string not
found in the list.
(b) binary search
(i) sort the given list and print sorted list.
(ii)find the mid position in the list by
giving starting and ending positions in
the list.
(iii)if string is found at mid position print
the position and exit.
(iv)if string is less than string at mid
position the repeat steps (ii) and
(iii)by taking beginning and mid
position-1 as our new list.
(v) if string is greater than string at mid
position the repeat steps (ii) and
(iii)by taking mid+1 and end of list
as our new list.
(vi) if string not found print string not
found in the list.

(E) Program :

#include
#include
#include

int binarysearch(char s[20][20],char str[20],int arrayStart,int arrayEnd,int c)
{
int m,i,j;
char st[20];
if(c==1){
for(i=0;i {
for(j=1;j {
if(strcmp(s[j-1],s[j])>0)
{ //exchange of contents
strcpy(st,s[j-1]);
strcpy(s[j-1],s[j]);
strcpy(s[j],st);
}
} //end of sorting
}

printf("\n\nsorted list of strings"); //printing sorted list
for(i=0;i {
printf("\n%s",s[i]);
}
} //search begins
if (arrayStart<=arrayEnd)
{
m=(arrayStart+arrayEnd)/2; //find the mid position
if (strcmp(s[m],str)==0) //compare the strings
return m;
else if (strcmp(str,s[m])<0) // call binary search in the one half of array
return binarysearch(s,str,arrayStart,m-1,-1);
else
return binarysearch(s,str,m+1,arrayEnd,-1);
}
return -1;
}

void linearsearch(char s[20][20],char str[20],int num)
{
int j, f=0;
for(j=0;j if( strcmp(s[j],str) == 0) //if element found print position
{
printf("\nThe string %s is present at position %d in list\n",str,j+1);
f=1;
break;
}
if(f==0) //if element not found then print
printf("\nThe string is %s is not present in the list\n",str);
}

void display(char s[20][20],int n)
{
int i; //display the strings
for(i=0;i {
printf("\n%s",s[i]);
}
}

void main()
{
char str[20],ch,s[20][20];
int n,i=0,c;
clrscr();
do
{ //read the strings
printf("\n enter the string:");
fflush(stdin);
scanf("%s",s[i++]);
printf("\n do you want to enter another string Y/N");
fflush(stdin);
scanf("%c",&ch);
n=i;
}while(ch!='n');
printf("\n n=%d",n);
display(s,n); //display the string list
printf("\n 1.linear search 2.binary search");
printf("\n enter your choice:"); //read the searching technique
scanf("%d",&c);
fflush(stdin);
printf("\n enter the string to be searched:");
scanf("%s",&str); //read the string to be searched
switch(c)
{
case 1:
linearsearch(s,str,n); //call linear search
break;

case 2: c=binarysearch(s,str,0,n,1); //call binary search
if(c==-1)
printf("\nstring not found in the list");
else
printf("\n the string %s is found at position %din sorted list",str,c+1);
break;
default : break;
}
getch();
}


(F) Testing :


S.NO Input Aspect to be Tested Expected Result
1 List of strings ={ba,jy,ch} Str = ba
String ar found at 1 position
2 List of strings ={ba,jy,ch} Str = ar String bg not found










(G) Limitations :
(i) the search list can have maximum of 20 strings and
each of which has maximum of 20 characters.
(ii) the length of string to be searched is restricted to 20
characters.