# 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(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) 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(log _{2}n)**.

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

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

What's New

- C Language MCQs
- Python MCQs
- Perl MCQs
- MongoDB MCQs
- Java MCQs
- C# MCQs
- Scala MCQs
- Blockchain MCQs
- AutoCAD MCQs
- PHP MCQs
- JavaScript MCQs
- jQuery MCQs
- ReactJS MCQs
- AngularJS MCQs
- JSON MCQs
- Ajax MCQs
- SASS MCQs
- HTML MCQs
- Advanced CSS MCQs
- CSS MCQs
- OOPs MCQs
- PL/SQL MCQs
- SQL MCQs
- Oracle MCQs
- SQLite MCQs
- MS Word MCQs
- Software Engineering MCQs
- Operating System MCQs
- Project Management MCQs
- Data Analytics and Visualization MCQs
- MIS MCQs
- Linux MCQs
- WordPress MCQs
- Blogging MCQs
- Marketing MCQs

- Generally Accepted Accounting Principles MCQs
- Bills of Exchange MCQs
- Business Environment MCQs
- Sustainable Development MCQs
- Marginal Costing and Absorption Costing MCQs
- Globalisation MCQs
- Indian Economy MCQs
- Retained Earnings MCQs
- Depreciation MCQs
- Partnership MCQs
- Sole Proprietorship MCQs
- Goods and Services Tax (GST) MCQs
- Cooperative Society MCQs
- Capital Market MCQs
- Business Studies MCQs
- Basic Accounting MCQs
- MIS Executive Interview Questions
- Go Language Interview Questions

Top Interview Coding Problems/Challenges!

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions!