Linear Search and Binary Search in C

Linear & Binary Search

Searching is the process to find a value in the given list of values. In an Array if we have to find an element or value then for that we use some SEARCH ALGORITHMS and two of them are-

⧫Linear Search

⧫Binary Search

Linear Search:

Linear Search which is also known as Sequential Search is used to search an element in an array. In this search-

• First we ask user to give the value for comparison.
• Then the compiler starts comparing the value to the values/elements present in the array.
• Comparison will start from one end to another end.(We can start from any side like from left to right or right to left, it totally depends on the way of writing the code)
• When the given value is founded to be equal to the element in the array then the comparison process gets stopped and you got the element.
• If the compiler checks each and every element in the array and the value  is not equal to any of the elements present in the array then element is not found.

NOTE: If the element that user want to search is present in the array more than one time then the first encounter with that element will be considered.

for eg: If we have to find the index of an element which has a value "28" in the below array

As there are two element which shares the same values "28", so in this case the compiler gives you the index of the element- " 1 " because it came first (generally we compares from left to right).

Some examples of Linear Search:-

@ Write a code to find the smallest element 

1. #include <stdio.h>
2.  
3. int main()
4. {
5.   int array[100], search, c, n;
6.  
7.   printf("Enter number of elements in array\n");
8.   scanf("%d", &n);
9.  
10.   printf("Enter %d integer(s)\n", n);
11.  
12.   for (c = 0; c < n; c++)
13.     scanf("%d", &array[c]);
14.  
15.   printf("Enter a number to search\n");
16.   scanf("%d", &search);
17.  
18.   for (c = 0; c < n; c++)
19.   {
20.     if (array[c] == search)    /* If required element is found */
21.     {
22.       printf("%d is present at location %d.\n", search, c+1);
23.       break;
24.     }
25.   }
26.   if (c == n)
27.     printf("%d isn't present in the array.\n", search);
28.  
29.   return 0;
30. }

Binary Search:

For the purpose of searching we use Binary Search too. But this search can only be used when the array is Bubble Sort i.e, in ascending order. Let understand it with an example. So in this search-

• First we ask user to give the value for comparison.
  Let the entered value is stored in variable "str".
  Let the user enters- CASE 1:  "20"  //first time
                                  CASE 2:  "30"  //second time
                                  CASE 3:  "40"  //third time
• Then we find the middle value of the array. And to find the middle value we use a formula-
  "middle = (highest index - lowest index) / 2" //Highest index = Number of elements - 1
  Here middle = (4-0)/2
                       = 2
• If the middle value is the value user want to search then comparison process gets stopped and you got the element.
  Here arr[ middle ]= =str  (for CASE 2)
• If that is not the value that then the compiler checks whether the given value is greater or lesser than the middle value.
  Here for CASE 1: str < arr[ middle ]
                CASE 3: str > arr[ middle ]

For CASE 3:

• The index of Lowest Element changes to the index of Middle Element and then it again find out the middle value using same formula.
  Here middle = (4+2) / 2 //here lowest index becomes "2"
                       = 3
• Now the compiler checks the the value with the given value
  Here arr[ middle ]= =str (for CASE 3)

For CASE 1:

• The index of Highest Element changes to the index of Middle Element and then it again find out the middle value using same formula.
  
  Here middle = (2-0) / 2 //here lowest index becomes "2"
                       = 1
• Now the compiler checks the the value with the given value
  
  Here arr[ middle ]= =str (for CASE 1)

Example of Binary Search:-

@ Write a program to search an element in an array using Binary Search ?

1. #include <stdio.h>
2.  
3. int main()
4. {
5.    int c, first, last, middle, n, search, array[100];
6.  
7.    printf("Enter number of elements\n");
8.    scanf("%d",&n);
9.  
10.    printf("Enter %d integers\n", n);
11.  
12.    for (c = 0; c < n; c++)
13.       scanf("%d",&array[c]);
14.  
15.    printf("Enter value to find\n");
16.    scanf("%d", &search);
17.  
18.    first = 0;
19.    last = n - 1;
20.    middle = (first+last)/2;
21.  
22.    while (first <= last) {
23.       if (array[middle] < search)
24.          first = middle + 1;    
25.       else if (array[middle] == search) {
26.          printf("%d found at location %d.\n", search, middle+1);
27.          break;
28.       }
29.       else
30.          last = middle - 1;
31.  
32.       middle = (first + last)/2;
33.    }
34.    if (first > last)
35.       printf("Not found! %d isn't present in the list.\n", search);
36.  
37.    return 0;  
38. }

Linear Search V/S Binary Search

• In Linear Search the compiler will go to the very first element of an Array whereas in Binary Search the compiler will go to element present in the middle of an Array.
• In Linear Search the compiler will not need the array to be sorted. But in Binary Search the array should be Bubble Sort.
• Binary Search is faster and better then Linear Search Algorithm.

Do check our post on Array and Bubble Sorting. (BUBBLE SORTING WILL BE AVAILABLE SOON) 

For giving some suggestion please comment us or check our "Contact us" page. Also more update related to coding will be added in this Blog later on, so please get attached with this Blog. Thank you for your support and time...