difference between linear search and binary search

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.

1 COMMENT

  1. you’re really a good webmaster. The website loading speed is incredible. It seems that you’re doing any unique trick. Furthermore, The contents are masterwork. you’ve done a excellent job on this topic!

LEAVE A REPLY

Please enter your comment!
Please enter your name here