# 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 _{2}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 _{2}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))

Related Tutorials

- Introduction to Algorithms
- Introduction to Greedy Strategy in Algorithms
- Stability in sorting
- External Merge Sorting Algorithm
- Radix Sort and its Algorithm
- Bucket Sort Algorithm
- Bubble sort Algorithm, Flow Chart and C++ Code
- Insertion sort Algorithm, flowchart and C, C++ Code
- Merge Sort | One of the best sorting algorithms used for large inputs
- Binary Search in C, C++
- Randomized Binary Search
- Meta Binary Search | One-sided Binary Search
- Binary Search in String
- Variants of Binary Search
- Sieve of Eratosthenes to find prime numbers
- Optimal Merge Pattern (Algorithm and Example)
- Given an array of n numbers, Check whether there is any duplicate or not
- Finding the missing number
- Find the number occurring an odd number of times
- Find the pair whose sum is closest to zero in minimum time complexity
- Find three elements in an array such that their sum is equal to given element K
- Bitonic Search Algorithm
- Check whether a number is Fibonacci or not
- Segregate even and odd numbers in minimum time complexity
- Find trailing zeros in factorial of a number
- Find Nearest Greatest Neighbours of each element in an array
- Interpolation search algorithm
- Floor and ceil of an element in an array using C++
- Two Elements whose sum is closest to zero
- Find a pair with a given difference
- Count number of occurrences (or frequency) in a sorted array
- Find a Fixed Point (Value equal to index) in a given array
- Find the maximum element in an array which is first increasing and then decreasing
- Dynamic Programming (Components, Applications and Elements)
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Dynamic Programming (Components, Applications and Elements)
- Find the Nth Fibonacci number | C++
- Longest Common Subsequence using Dynamic programming (DP)
- Longest Increasing Subsequence using Dynamic programming (DP)
- Find the maximum sub-array sum using KADANE'S ALGORITHM
- Non-intersecting chords using Dynamic Programming (DP)
- Edit Distance using Dynamic Programming (DP)
- Finding Ugly Number using Dynamic Programming (DP)
- Egg dropping problem using Dynamic Programming (DP)
- Wild card matching problem using Dynamic programming (DP)
- Compute sum of digits in all numbers from 1 to N for a given N
- Minimum jumps required using Dynamic programming (DP)
- Graph coloring problem's solution using backtracking algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- Travelling Salesman Problem
- Kruskal's (P) and Prim's (K) Algorithms
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code

- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Find the GCD (Greatest Common Divisor) of two numbers using EUCLID'S ALGORITHM
- Compute the value of A raise to the power B using Fast Exponentiation
- Implement First Come First Served (FCFS) CPU Scheduling Algorithm using C program
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Analysis of LRU page replacement algorithm and Belady's anomaly
- Branch and Bound
- Find the roots of a complex polynomial equation using Regula Falsi Method in C
- Sieve of Eratosthenes to find prime numbers
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Divide and Conquer Paradigm (What it is, Its Applications, Pros and Cons)
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Jump Search Implementation using C++
- Optimal Merge Pattern (Algorithm and Example)
- Introduction to Greedy Strategy in Algorithms
- Strassen's Matrix Multiplication in algorithms
- Huffman Coding (Algorithm, Example and Time complexity)
- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Graph coloring problem's solution using backtracking algorithm
- Tournament Tree and their properties
- Deterministic and Non Deterministic Algorithms
- Lower Bound Theory
- Non Recursive Tree Traversal Algorithm
- Line Drawing Algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- P and NP problems and solutions | Algorithms
- Travelling Salesman Problem
- 2 – 3 Trees Algorithm
- Kruskal's (P) and Prim's (K) Algorithms
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Midpoint Circle Algorithm
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code
- Reliability design problem
- Removing consecutive duplicates from a string
- Fast Exponentiation using Bitmasking

Comments and Discussions!