[ Searching ]
Sorting should have
been given before searching but as Bubble Sort is used for Binary Search. Next
week posting will be on sorting
Linear Search –
Search for an element in an Array. Linear search through the whole array until
last the element. It is very slow and having complexity – O(n).
Finding the a
Number in an array using Linear Search.
#include <stdio.h>
#include <conio.h>
//Linear Search
int
main()
{
int
NO[20],n,num,i,flag=0;
printf("\n\tEnter
Numbers of Input (below 20 ) : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\tEnter
Element at [%d] : ",i+1);
scanf("%d",&NO[i]);
}
printf("\n\n\tEnter
Number to Search : ");
scanf("%d",&num);
printf("\n\n\t
Numbers in Array : ");
for(i=0;i<n;i++)
{
printf("%d ",NO[i]);
}
for(i=0;i<n;i++)
{
if(num==NO[i])
{
flag=1;
break;
}
}
if(flag==1)
{
printf("\n\n\t%d
is present in %d position ",num,i+1);
}
else
{
printf("\n\n\t%d
is not present ",num);
}
getch();
return 0;
}
Counting the number of times an
given number is presents in an array using Linear Search.
#include <stdio.h>
#include <conio.h>
// Counting using Linear Search
int
main()
{
int
NO[20],n,num,i,flag=0;
printf("\n\tEnter
Numbers of Input (below 20 ) : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\tEnter Element
at [%d] : ",i+1);
scanf("%d",&NO[i]);
}
printf("\n\n\tEnter
Number to Search : ");
scanf("%d",&num);
printf("\n\n\t
Numbers in Array : ");
for(i=0;i<n;i++)
{
printf("%d ",NO[i]);
}
for(i=0;i<n;i++)
{
if(num==NO[i])
{
flag++;
}
}
if(flag>0)
{
printf("\n\n\t%d
is present and repeated %d times ",num,flag);
}
else
{
printf("\n\n\t%d
is not present ",num);
}
getch();
}
Searching a Text using Linear Search
#include <stdio.h>
#include <conio.h>
#include <string.h>
//Searching String using Linear
Search
int
main()
{
char
word[5][20],wd[20];
int
i,flag=0;
for(i=0;i<5;i++)
{
printf("\tEnter
Word at [%d] : ",i+1);
gets(word[i]);
}
printf("\n\n\tEnter
Word to Search : ");
gets(wd);
printf("\n\n\t
Words in Array : ");
for(i=0;i<5;i++)
{
printf("%s ",word[i]);
}
for(i=0;i<5;i++)
{
if(strcmpi(word[i],wd)==0)
{
flag=1;
break;
}
}
if(flag==1)
{
printf("\n\n\t%s
is present in %d position ",wd,i+1);
}
else
{
printf("\n\n\t%s
is not present ",wd);
}
getch();
}
Finding the a Number in an array
using Binary Search. Binary search required an sorted array.
At each iteration, the length of
the new subarray to be searched is
approximately half of the previous one.
Searching start from Mid-point.
1st iteration: 1 possible value
2nd iteration: 2 possible values
(left half or right half)
3rd iteration: 4 possible values
(left of left half, right of left half, right of right half, right of left
half)
nth iteration: 2n-1 possible
values
Binary search algorithm has
logarithmic complexity θ ( log n ).
#include <stdio.h>
#include <conio.h>
//Binary Search
void sort(int x[],int n)
{
int i,j,temp;
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
{
if(x[j]>x[j+1])
{
temp=x[j];
x[j]=x[j+1];
x[j+1]=temp;
}
}
}
}
int
main()
{
int
n,i,j,first=0,last,mid,arr[10],s,flag=0;
printf("Enter
a nos. of Input : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter
Element at [%d] : ",i+1);
scanf("%d",&arr[i]);
}
printf("\nEnter
no to search ");
scanf("%d",&s);
printf("\n\n\tOriginal
\n\n\t");
for(i=0;i<n;i++)
{
printf("%d
",arr[i]);
}
sort(arr,n);
printf("\n\n\tAfter
Sorting \n\n\t");
for(i=0;i<n;i++)
{
printf("%d
",arr[i]);
}
first=0;
last=n-1;
mid=0;
while(first<=last)
{
mid=(first+last)/2;
if(arr[mid]==s)
{
flag=1;
break;
}
else
if(arr[mid]<s)
{
first=mid+1;
}
else
{
last=mid-1;
}
}
if(flag==1)
{
printf("\n\t%d
is present in %d postion",s,mid+1);
}
else
{
printf("\n\t%d
is not present",s);
}
getch();
return 0;
}
Searching a Text using Binary Search
#include <stdio.h>
#include <conio.h>
#include <string.h>
//Binary Search for String
void sort(char x[5][20])
{
int
i,j;
char
temp[20];
for(i=0;i<5;i++)
{
for(j=0;j<5-i-1;j++)
{
if(strcmpi(x[j],x[j+1])>0)
{
strcpy(temp,x[j]);
strcpy(x[j],x[j+1]);
strcpy(x[j+1],temp);
}
}
}
}
int
main()
{
int
i,j,first=0,last,mid,flag=0;
char
arr[5][20],s[20];
for(i=0;i<5;i++)
{
printf("Enter
word at [%d] : ",i+1);
gets(arr[i]);
}
printf("\nEnter
word to search ");
gets(s);
printf("\n\n\tOriginal
\n\n\t");
for(i=0;i<5;i++)
{
printf("%s
",arr[i]);
}
sort(arr);
printf("\n\n\tAfter Sorting
\n\n\t");
for(i=0;i<5;i++)
{
printf("%s
",arr[i]);
}
first=0;
last=4;
mid=0;
while(first<=last)
{
mid=(first+last)/2;
if(strcmpi(arr[mid],s)==0)
{
flag=1;
break;
}
else
if(strcmpi(arr[mid],s)<0)
{
first=mid+1;
}
else
{
last=mid-1;
}
}
if(flag==1)
{
printf("\n\t%s
is present in %d position",s,mid+1);
}
else
{
printf("\n\t%s
is not present",s);
}
getch();
return 0;
}
No comments:
Post a Comment