Linear vs Binary Search: Data Structure

Difference Between Linear and Binary Search

What is Linear Search?

A linear search also referred as a sequential search. It is a way to find an element within a list and it scans a list without skipping any element or we can say it searches a whole list sequentially until a match is found or the whole list has been searched. Once element has found then it returns the position of that element in the list.

Example:

Complexity of Linear Search

As linear search scans list elements one by one without skipping any element until a match is found or the whole list has been scanned. So, the time complexity of the linear search depends on the number of elements present in the list which O(n) where n is the number of elements present in the list in worst case scenario.

Binary Search

Binary search is another way to find an element in the list. In binary search, we calculate the middle element and check the middle element is greater or smaller than the element which we want to search in the list. Binary search algorithm doesn’t search the list sequentially or we can say it doesn’t scan each element present in the list. It searches a sorted list or array by dividing it in to the half. The binary search algorithm takes less time to search an element in list over the linear search algorithm.

For using the binary search algorithm, we need to consider one thing which is array or list must be sorted. The binary search uses the divide and conquers technique, in which array or list will be divided recursively.

Here we will try to understand cases used in Binary Search:

Case 1: element<array [mid] then left = mid+1.

Case 2: element>array [mid] then right=mid-1

Case 3: element = array [mid] // element is found

Example:

Complexity of Binary Search         

The time complexity of binary search is O(log n) because in binary search, we search an element in half of list by dividing it recursively.

Difference Between Linear and Binary Search

Parameters	Linear search	Binary search
Definition	A linear search also referred as a sequential search. It is way to find an element within a list and it scans a list without skipping any of element or we can say it searches a whole list sequentially until a match is found or the whole list has been searched.	Binary search is another way to find an element in the list. In binary search, we calculate the middle element and check the middle element is greater or smaller than the element which we want to search in the list.
Sorted data	There is no requirement of sorted data. The linear search can work on both sorted and unsorted data.	In Binary Search, the array must be sorted then only we can apply the algorithm.
Technique  used	The linear search is based on sequential technique.	The binary search is based on the divide and conquers technique.
Worked on	It can be used on small data.	It can be used for large data.
Algorithm efficiency	The linear search is not efficient as compared to binary search.	The binary search takes less time to search an element over the linear search.
Time complexity in worst-case	The time complexity of the linear search depends on the number of elements present in the list which is O(n) where n is the number of elements present in the list	The time complexity of binary search is O(log n).