Linear Search VS Binary Search

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();

}

Download Source code

Next Topic