C Program to Compare Binary and Sequential Search

«
»
This C program compares two searching algorithms – Binary and Sequential Search.

Sequential search is used to find a key in a randomly arranged array. Searching time is O(n). Binary search on the other hand is implemented in a sorted array and is much faster than linear search. Its time complexity is O(log(n)).

Here is the source code of the C program to compare binary and sequential searching algorithms. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

advertisement
  1. #include <stdio.h>
  2. #define MAX 10
  3. int linearsearch(int numbers[], int key)
  4. {
  5.     int i;
  6.     for (i = 0; i < MAX; i++)
  7.     {
  8.         if (key == numbers[i])
  9.             return i;
  10.     }
  11.     return -1;
  12. }
  13. int binarysearch(int numbers[], int key)
  14. {
  15.     int l = 0, u = MAX - 1;
  16.     int c, mid;
  17.      while (l <= u){
  18.          mid = (l + u) / 2;
  19.          if (key == numbers[mid]){
  20.              return mid;
  21.          }
  22.          else if (key < numbers[mid]){
  23.              u = mid - 1;
  24.          }
  25.          else
  26.              l = mid + 1;
  27.     }
  28.     return -1;
  29. }
  30. int main() {
  31.     int numbers[MAX];
  32.     int i;
  33.     int index, key;
  34.     printf("Enter %d numbers : ", MAX);
  35.     for (i = 0; i < MAX; i++)
  36.     {
  37.         scanf("%d", &numbers[i]);
  38.     }
  39.     printf("\nEnter a key to find using linear search: ");
  40.     scanf("%d", &key);
  41.     index = linearsearch(numbers, key);
  42.     if ( index >= 0)
  43.         printf("\n%d found at index %d using linear search.", key, index);
  44.     else
  45.         printf("\nNot found!!");
  46.     printf("\nEnter %d numbers in increasing order: ", MAX);
  47.     for (i = 0 ; i < MAX; i++)
  48.         scanf("%d", &numbers[i]);
  49.     printf("\nEnter a key to find using binary search: ");
  50.     scanf("%d", &key);
  51.     index = binarysearch(numbers, key);
  52.     if (index >= 0 )
  53.         printf("Found at index %d", index);
  54.     else
  55.         printf("\nNot found!!!");
  56.  
  57.     return 0;
  58.     }

$ gcc comparesearch.c -o comparesearch
$ ./comparesearch
 
Enter 10 numbers : 1 21 45 66 98 85 78 4 55 48
Enter a key to find using linear search: 45
45 found at index 2 using linear search.
Enter 10 numbers in increasing order: 13 21 45 66 98 99 112 155 185 202 
Enter a key to find using binary search: 66 
Found at index 3

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Reference Books in C Programming, Data Structures and Algorithms.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter