A linear search works by looking at each element in a list
of data until it either finds the target or reaches the end. This results in
O(n) performance on a given list. A binary search comes with the prerequisite
that the data must be sorted. We can leverage this information to decrease the
number of items we need to look at to find our target. We know that if we look
at a random item in the data (let's say the middle item) and that item is
greater than our target, then all items to the right of that item will also be
greater than our target. This means that we only need to look at the left part
of the data. Basically, each time we search for the target and miss, we can
eliminate half of the remaining items. This gives us a nice O(log n) time
complexity.
Just remember that sorting data, even with the most
efficient algorithm, will always be slower than a linear search (the fastest
sorting algorithms are O(n * log n)). So you should never sort data just to
perform a single binary search later on. But if you will be performing many
searches (say at least O(log n) searches), it may be worthwhile to sort the
data so that you can perform binary searches. You might also consider other
data structures such as a hash table in such situations.
Image Source : https://en.wikipedia.org/wiki/Binary_search_algorithm
Example : Array is best example of linear search and tree
binary search.Program Linear Search Vs Binary Search
#include<stdio.h>
#include<conio.h>
#define MAX 5
void main()
{
int lar[MAX],bar[MAX],i,n,m;
clrscr();
printf("\nInput for linear
search array>>\n");
for(i=0;i<MAX;i++)
{
printf("Enter
number>> ");
scanf("%d",&lar[i]);
}
printf("\nInput for Binar
search array>>\n");
printf("Enter only sorted
number>>\n");
for(i=0;i<MAX;i++)
{
printf("Enter
number>> ");
scanf("%d",&bar[i]);
}
printf("Enter number for
search>> ");
scanf("%d",&n);
for(i=0;i<MAX;i++)
{
if(lar[i]==n)
break;
}
if(i==MAX)
printf("\nSearch Number
not found by linear search\n");
else
printf("Number found at %d index by linear search",i);
/* calculate middle index of binary
search array*/
m=MAX/2;
if(bar[m]==n)
printf("\nNo found at %d
index binary search\n",m);
else
{
if(n>bar[m])
{
/* right search because
search number is greater than middle index number*/
for(i=m;i<MAX;i++)
{
if(n==bar[MAX])
break ;
}
if(i==MAX)
printf("\nSearch
number not found\n");
else
printf("\nNo
found at %d index by binary search\n",i);
}
else
{
/* left search because search
number is less than middle index number*/
for(i=m;i<MAX;i--)
{
if(n==bar[MAX])
break;
}
if(i==MAX)
printf("\nSearch
number not found\n");
else
printf("\nNo
found at %d index by binary search\n",i);
}
}
getch();
}
No comments:
Post a Comment