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

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

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