Difference Between Linear Search and Binary Search
Difference Between Linear Search and Binary Search: When it comes to the search operation in programming, two names come in mind. Linear search and binary search. Some people confuse in these terms. So let’s see what are the difference between liner search and binary search?
What is Linear search?
Linear search is a simple searching algorithm. In this type of search, the searching process occurs from one item after the other. Means this search algorithm checks every item present and checks for a matching item on that.
Searching starts from the first item. If the item does not match, then it moves to the second item and does the same. It continues the same process until it finds the match.
In a linear search, the efficiency of the algorithm determined by the number of comparisons to search an element or time consumption in the process. If the element we are searching for, is in the first position of the data structure, then it requires only one comparison. In this case, the efficiency will be good because it takes less time to find the item. When the element we are searching for, is in the last position, then it requires an N number (number of data items) of comparisons to find the element.
The pseudocode of linear search algorithms look like this –
procedure linear_search (list, value)
for each item in the list
if match item == value
return the item’s location
end if
end for
end procedure
Also, read – DDR3 vs DDR3L and DDR4 vs DDR4L | Difference between DDR3 and DDR3L
What is a Binary search?
The binary search algorithm is faster as compared to a linear search. To perform this search, the data collection should be in the sorted form. The search algorithm finds the item by start comparing from the middle most item of the collection.
To determine the middle of any collection, it uses a formula.
Mid = low + (high – low) / 2
Low and high refers to the position number (Like 0, 1, 2, 3, 4 etc) which starts from the left.
If a match occurs in the middle position, then the index of the item is returned. If the middle item is greater than the searched item, then it searches in the sub-array to the left of the middle item. Otherwise, it searches in the sub-array to the right of the middle item. With each search, the number of items to search decreases each time. This same process continues on the sub-array then sub-array, until the size of the sub-array reduces to zero.
The pseudocode of binary search algorithms look like this –
Procedure binary_search
A ← sorted array
n ← size of an array
x ← value to be searched
Set lowerBound = 1
Set upperBound = n
while x not found
if upperBound < lowerBound
EXIT: x does not exist.
set midPoint = lowerBound + ( upperBound – lowerBound ) / 2
if A[midPoint] < x
set lowerBound = midPoint + 1
if A[midPoint] > x
set upperBound = midPoint – 1
if A[midPoint] = x
EXIT: x found at location midPoint
end while
end procedure
Also, read – Computer Full Form | Computer Related Full Form
Difference between linear search and binary search
As of now, we have seen some of the basic things related to both of these searches. Based on that you may differentiate some points as well. But let’s try to grab most and see what are the major difference between linear search and binary search.
|
Linear search |
Binary search |
|
In a linear search, it scans one item at a time in a sequential basis without jumping to any item |
Binary search divides the whole array to half and starts searching. If not found then it searches in the left or right sub-array |
|
Input data need not to be sorted in linear search |
Input data needs to be sorted in before starting the binary search |
|
Also called sequential search |
Also called logarithmic search or half-interval search |
|
Time complexity is O(N) |
Time complexity is O(log2N) |
|
Best case is to find the element in the first position |
Best case is to find the element in the middle position |
|
Take more time |
Take less time |
|
Less efficient |
More efficient |
| Less complex |
More complex |
Conclusion
Linear search and binary search both are used to search an element in a data structure such as an array. Of course, binary search is more efficient than the linear search but the elements should be shorted in the array. These are some of the difference between linear search and binary search you may consider. Depending on the requirements, you can choose one of them.