Home » Algorithms

Linear Vs. Binary Search: Comparisons & Key Differences

Difference between linear and binary Search: In this tutorial, we will learn about the library and binary search, and their similarities and differences based on the different factors. By Radib Kar Last updated : August 14, 2023

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. Linear Vs. Binary Search: Input Range

For the linear search, the input range doesn't need to be sorted. It works on both unsorted and sorted arrays, whereas for binary search, the input range must be sorted, otherwise, it will fail.

2. Linear Vs. Binary Search: Time Complexity

Linear search has linear time complexity, O(n) where n is the number of elements in the input range, whereas, binary search has logarithmic time complexity, O(log₂n) 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. Linear Vs. Binary Search: Algorithm Type

Linear search is iterative. It searches sequentially, and iteratively (Though we can implement linear search recursively) while 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. Linear Vs. Binary Search: 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, while 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. Linear Vs. Binary Search: 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, while in binary search, also the worst-case complexity is O(log₂n).

6. Linear Vs. Binary Search: 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 searching technique is better, Linear or 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)

Linear Vs. Binary Search in C++ STL

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))