Register Login

Difference between Linear Search and Binary Search

Updated Jan 10, 2020

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

BASIS FOR COMPARISON LINEAR SEARCH BINARY SEARCH
Time Complexity The formula can be written as O(N) O(log 2 N) is the formula that can be followed for this search
Sequential Linear search is led by sequence; it starts from the first point and ends at the last point. The binary search begins from the middle point.
The most compelling case time The first Element serves to the most appropriate case time Centre Element is the most relevant case time in this search.
Prerequisites needed for an array Not needed The array must be formed in sorted order
The worst-case scenario for n elements N number of comparisons will be needed The conclusion can be derived only after log2N comparisons
Capable of being implemented on Linked lists and arrays Incapable of being implemented directly on linked lists
Insert operation Can be inserted with ease at the end of lists Processing is needed to make insertions at their proper place and for the sake of maintaining sorted lists.
Algorithm type Iterative characteristics depicted Characteristics of “divide and conquer” features are described.
Utility Easy to decipher and apply. There is no need for ordered elements. The algorithms are tricky to understand and apply. The elements have to be organized in the proper manner and order.
Lines of Coding Less More

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

Key differences between binary search and linear search

  1. While a linear search is repetitive or iterative in nature as well as uses the sequential approach, the binary search goes about its task by using the divide and conquer strategy.
  2. The time complexity of binary search has O(log2N), while the time complexity of linear search happens to be O(N).
  3. The best-case scenario for a time in a linear search c program is for the 1st element, which is O(1). In comparison, in the case of binary search, the search is for the middle element, which is O(1).
  4. In the case of C program linear search, the worst-case scenario for searching an element happens to be equivalent to N number of comparisons. On the other hand, in the case of c program binary search, the worst-case stands at log2N number of similarities.
  5. Linear searches may be implemented in an array and linked lists. On the other hand, binary searches are not capable of being implemented on linked lists directly.
  6. A binary search in c programming language needs sorted arrays for effective performance. It necessitates processing for making insertions at their proper place and maintaining sorted lists. In comparison, linear search in c programming language does not require the requirement of sorted elements; therefore, the elements are conveniently inserted at the bottom of the list.
  7. As there is no requirement for ordered elements, linear search in c becomes an easy process for programmers. Conversely, the binary search algorithms are tricky, with the elements being necessarily arranged in a given order.
  8. Input data has to be sorted in case of binary search, but the same can be avoided in linear search.

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.


Comments

  • 07 Jul 2017 12:24 pm Guest Helpful Answer

    Linear Search: It is a sequential search or it searches line by line. So it is slow and it takes too much time to find out the data, it is also know as Sequential Search.

    Binary Search: In Binary search it divide the table into two parts, a lower value part and an upper-value part, after dividing It will check with the middle value if its lesser than the searched element than it goes to right half else it goes to left half. Therefore it is necessary that the search field of the table should be in Ascending order. If you sort the list in descending order then binary search fails.

    You can't use BINARY SEARCH with SORTED or HASHED tables - you'll get a syntax error. BINARY SEARCH is used for internal table, you must Sort your Internal Table in ASCENDING order for BINARY SEARCH.

    E.g suppose we have 5 sales order like this and you have to find 100033:

    100010

    100011

    100022

    100033

    100044

    so linear search will start search from 100010 to 100011 to 100022 and then 100033.

    we proceed 1 by 1 : it takes 4 iterations

    Binary search:

    In binary search it breaks the list into two parts and take middle value(100022) compare with 100033 now we are left with

    100033,100044

    we compare (100033) and (100044) with 100033

    Thus process completed in 2 iterations. so it is very fast.

    Binary search must be preferred over linear search.

  • 23 Feb 2018 7:36 pm Prashant Muttepawar Helpful Answer
    hi,If you read entries from standard tables using a key other than the default key, you can use a binary search instead of the normal linear search. To do this, include the addition BINARY SEARCH in the corresponding READ statements.READ TABLE WITH KEY = ... = BINARY SEARCH.The standard table must be sorted in ascending order by the specified search key. The BINARY SEARCH addition means that you can access an entry in a standard table by its key as quickly as you would be able to in a sorted table.REPORT demo_int_tables_read_index_bin.DATA: BEGIN OF line,col1 TYPE i,col2 TYPE i,END OF line.DATA itab LIKE STANDARD TABLE OF line.DO 4 TIMES.line-col1 = sy-index.line-col2 = sy-index ** 2.APPEND line TO itab.ENDDO.SORT itab BY col2.READ TABLE itab WITH KEY col2 = 16 INTO line BINARY SEARCH.WRITE: 'SY-SUBRC =', sy-subrc.The output is:SY-SUBRC = 0The program fills a standard table with a list of square numbers and sorts them into ascending order by field COL2. The READ statement uses a binary search to look for and find the line in the table where COL2 has the value 16.Linear search use sequential search means each and every reord will be searched to find. so it is slow.Binary search uses logrim for searching. Itab MUST be sorted on KEY fields fro binary search. so it is very fast.The search takes place as follows for the individual table types :standard tables are subject to a linear search. If the addition BINARY SEARCH is specified, the search is binary instead of linear. This considerably reduces the runtime of the search for larger tables (from approximately 100 entries upwards). For the binary search, the table must be sorted by the specified search key in ascending order. Otherwise the search will not find the correct row.sorted tables are subject to a binary search if the specified search key is or includes a starting field of the table key. Otherwise it is linear. The addition BINARY SEARCH can be specified for sorted tables, but has no effect.For hashed tables, the hash algorithm is used if the specified search key includes the table key. Otherwise the search is linear. The addition BINARY SEARCH is not permitted for hashed tables.Binary search must be preffered over linear sarch.

×