Difference between Linear Search and Binary Search

Binary search and linear search are two different techniques used in arrays for searching elements. The process of finding a specific element within a given list of elements, as stored randomly or in any order, is termed as Searching. In this article, we intend to throw light on what is binary search in c and linear search in c. We will also talk about the difference between linear search and binary search to help you understand the use of linear and binary searches in programming. Read on for a closer look at these topics.

Linear Search Vs. Binary Search

Comparison Chart

Binary Search in C

Binary search serves to be an essential algorithm. This kind of search technique is less cumbersome and takes comparatively less time for searching any given item and with minimum possible comparisons in place. The array elements are to be sorted before other things to conduct the binary search. Below, we help you understand the logic that lies behind the technique of binary search.

1. Firstly, the search for the middle element related to the array.
2. The array’s middle element is compared to the element to be searched.

Three scenarios can arise:

• The search is considered to be successful in case the element turns out to be the required element.
• In case the element is not equal to or greater than the desired item, then only the 1st half of the array is to be searched.
• In case the element is higher than the desired item, then only the 2nd half of the array is to be searched.

These steps have to be iterated in the binary search program in c until a specific element is exhausted or found in the search area. In this kind of algorithm, there is a reduction in each time search area. Thus, at the maximum limit, the total number of comparisons will be log (N+1). Given these benefits, the binary search is considered to be a more efficient algorithm in comparison to linear search. However, it is essential to sort out the array before the binary search is conducted. In a nutshell, binary search in c program reduces the time taken for a search to fifty percent its size once the middle of a sorted list is used.

Code Example of Binary Search in C

#include <stdio.h>
#include <conio.h>

void main ()
{
    int c, first, last, middle, n, search, array[100];
    clrscr();
    printf("Enter number of elements \n");
    scanf("%d",&n);

    printf("Enter %d integers\n",n);

    for (c=0; c < n; c++)
        scanf("%d",&array[c]);

    printf("Enter value to find\n");
    scanf("%d",&search);

    first = 0;

    last = n - 1;

    middle = (first+last)/2;

    while( first <= last){
        if(array[middle] < search)
        first = middle + 1;
        else if(array[middle] == search)
        {
            printf("Found at Location %d.\n",search , middle+1);
            break;
        }
        else
        last = middle - 1;

        middle = (first + last)/2;

        if (first > last)
        printf("Not Found! %d is not present in this list. \n",search);
        getch();
    }

}

Linear Search in C

In a linear search, every single element present in an array is searched for and retrieved one by one. The search is conducted in a logical order wherein it is figured out whether a given element is the desired element or not. In case the desired element is not found, then the search is considered to be an unsuccessful one after all the elements have been accessed. In the worst-case scenario, half the size (n/2) of the array has to be scanned in most cases to yield the desired result. Given this, linear search is best defined as a technique that traverses across the array sequentially and to locate any item.

The number of comparisons made or the time involved in searching a given record in a search table will determine the efficiency of the technique. Just a single comparison is said to be made in case the desired file is found in the very first position of the given search table. More comparisons, or in other words, n comparisons are to be made in case the desired record happens to be the last one in the lot. In the case of a linear search program in c, a given file is to be present at any point in the search table, then on an average, the total number of comparisons is likely to stand at (n+1/2) in c program for linear search. In the worst-case scenario of efficiency, O(n) would stand for the execution order.

Code Example of Linear Search in C

#include <stdio.h>
#include <conio.h>

void main ()
{

    int a[40], key, N, flag = 0, i;
    clrscr();

    printf("Enter the array limit \n");
    scanf("%d",&n);

    printf("Enter %d elements \n",N);

    for(i=0;i<N;i++)
    {
        scanf("%d",&a[i]);
    }

    printf("Enter the number to be searched \n");
    scanf("%d",&key);

    for(i=0;i<N;i++)
    {
        if(a[i] == key)
        {
            flag = 1;
            break;
        }
    }

    if(flag == 1)
    {
        printf("\nSearch Successful");
    }else
    {
        printf("\nSearch Failed");
    }
    getch();
}

Conclusion

C program for binary search or a linear search? Which way will you go? While linear search performs with the help of sequential access, binary searches are known to access data randomly. In case you have any further inputs regarding linear search vs. binary search, then please write to us in the Comments section below. We will wait to hear from you.