Performance comparison between Linear Search and Binary Search
Linear search is more simpler than binary search because linear search searches element from array or linked list by testing each of the element one by one and compare it with the search element starting from left to right but the binary search compares the target element from the middle of the element of array; if it is not found then half in which target cannot lie is eliminated and the search continues in the remaining half until the desired target is found. But the binary search is more efficient than the linear search because it takes less amount of comparisons to find target element as compare to linear search. But the insertion of elements in binary search is not more efficient because it requires arranged elements in specific order. Comparison of linear search and binary search can be taken to a table as below,
Difference between these two methods can represent graphically as below,
- Linear Search to find the element “J” in a given sorted list from A-X
- · Binary Search to find the element “J” in a given sorted list from A-X
Therefore, both linear and binary search algorithms can be useful depending on the application. When an array is the data structure and elements are arranged in sorted order, then binary search is preferred for quick searching. If linked list is the data structure regardless how the elements are arranged, linear search is adopted due to unavailability of direct implementation of binary search algorithm.
The typical Binary search algorithm cannot be employed to linked list because linked list is dynamic in nature and it is not known where the middle element is actually assigned. Hence, there is a requirement to design the variation of the binary search algorithm that can work on linked list too because the binary search is faster in execution than a linear search. Cheers!!
