Difference between Linear Search and Binary Search

Linear Search vs Binary Search: Here, we are going learn the difference between linear search and binary search with examples.
Submitted by Radib Kar, on July 20, 2020

Two popular search methods are linear and binary search. Both are heavily used. In searching key within a range. But both have lots of differences which are listed below,

1) Input range:

For the linear search, the input range doesn't need to be sorted. It works on a both unsorted and sorted array.

For binary search, the input range must be sorted, otherwise, it will fail.

2) Time complexity:

Linear search has linear time complexity, O(n) where n is the number of elements in the input range.

Binary search has logarithmic time complexity, O(log2n) where n is the number of elements in the input range.

Below is the example which shows how faster binary search work provided the input range is sorted?

#include <bits/stdc++.h>
using namespace std;

int linear_search(vector<int> arr, int key)
{
    for (int i = 0; i < arr.size(); i++)
        if (arr[i] == key)
            return i;

    return -1;
}

int binary_search(vector<int> arr, int key)
{
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == key)
            return mid;
        else if (arr[mid] < key)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1;
}

int main()
{
    vector<int> arr(10000000);
 
    //sorted input 1 to 10000000
    for (int i = 0; i < 10000000; i++)
        arr[i] = i + 1;

    //we will search 5 keys
    //key1=3000000
    //key2=5000000
    //key3=7000000
    //key4=9000000
    //key5=11000000
 
    vector<int> keys{ 3000000, 5000000, 7000000, 9000000, 11000000 };
    
    clock_t tStart1 = clock();
    
    // Linear Search time
    for (int i = 0; i < 5; i++) {

        int res = linear_search(arr, keys[i]);
        if (res != -1)
            cout << "Key found at : " << res << endl;
        else
            cout << "Key not found\n";
    }
    
    clock_t tend1 = clock();
    
    printf("Time taken in linear search: %.2fs\n", (double)(tend1 - tStart1) / CLOCKS_PER_SEC);

    clock_t tStart2 = clock();
    
    // Binary Search time
    for (int i = 0; i < 5; i++) {
        int res = binary_search(arr, keys[i]);
        if (res != -1)
            cout << "Key found at : " << res << endl;
        else
            cout << "Key not found\n";
    }
    
    clock_t tend2 = clock();
    
    printf("Time taken in binary search: %.2fs\n", (double)(tend2 - tStart2) / CLOCKS_PER_SEC);

    return 0;
}

Output:

Key found at : 2999999
Key found at : 4999999
Key found at : 6999999
Key found at : 8999999
Key not found
Time taken in linear search: 0.49s
Key found at : 2999999
Key found at : 4999999
Key found at : 6999999
Key found at : 8999999
Key not found
Time taken in binary search: 0.18s

3) Algorithm Type:

Linear search is iterative. It searches sequentially, iteratively (Though we can implement linear search recursively)

Binary search is divide & conquer type. It divides the range into two-part left and right and keeps finding recursively. (Though we can implement binary search iteratively)

4) Best case comparison:

In a linear search, the best case time complexity is O(1). It occurs when the searching key is the first element.

In binary search, also the best case complexity is O(1). It occurs when the searching key is in the middle of the sorted list.

5) Worst case comparison:

In a linear search, the worst-case time complexity is O(n). It occurs when the searching key is the last element.

In binary search, also the worst-case complexity is O(log2n).

6) Data structure Type:

Linear search can be easily implemented on any linear container (Vector, Single linked list, double linked list). A binary search can be implemented on data structures where two-way traversal is possible. We can't implement a binary search on a single linked list as we can't traverse in both directions.

Which one is better b/w linear search and binary search?

If the searching range is not sorted, then we should go for a linear search. Because to sort the time complexity would be O(n) even if we use counting sort. So, there is no use of binary search here. But, if the searching range is sorted then binary search is, of course, a better choice as worst-case complexity is Log(n) where for linear search it is O(n)

C++ STL using linear search, binary search

In C++ STL, we have a function binary_search() which use binary search algorithm. In C++ STL, find() uses linear search algorithm.

Detail of time complexity comparison b/w these two searching algorithms:

Best case:

  • Both O(1)

Average Case:

  • Linear search: O(n)
  • Binary search: O(log(n))

Worst case:

  • Linear search: O(n)
  • Binary search: O(log(n))





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.