Binary Search vs Linear Search
Linear search, also known as the sequential search is the simplest search algorithm. It searches for a specified value in a list by checking every element in the list. Binary search is also a method used to locate a specified value in a sorted list. Binary search method halves the number of elements checked (in each iteration), reducing the time taken to locate the given item in the list.
What is Linear Search?
Linear search is the simplest searching method, which checks each element in a list sequentially until it finds a specified element. The input to the linear search method is a sequence (such as an array, collection or a string) and the item that needs to be searched. The output is true if the specified item is within the provided sequence or false if it is not in the sequence. Since this method checks every item in the list until the specified item is found, in the worst case it will go through all the elements in the list before it finds the required element. The complexity of linear search is o(n). Therefore it is considered to be too slow to be used when searching elements in large lists. But this is very simple and easier to implement.
What is Binary Search?
Binary search is also a method used to locate a specified item in a sorted list. This method starts by comparing the searched element to the elements in the middle of the list. If the comparison determines that the two elements are equal the method stops and returns the position of the element. If the searched element is greater than the middle element, it starts the method again using only the bottom half of the sorted list. If the searched element is less than the middle element, it starts the method again using only the top half of the sorted list. If the searched element is not within the list, the method will return a unique value indicating that. Therefore the binary search method halves the number of elements compared (in each iteration), depending on the result of the comparison. Consequently, binary search runs in logarithmic time resulting in o(log n) average case performance.
What is the difference between Binary Search and Linear Search?
Even though both linear search and binary search are searching methods they have several differences. While binary search operates on sorted lists, liner search can operate on unsorted lists as well. Sorting a list generally has an average case complexity of n log n. linear search is simple and straightforward to implement than the binary search. But, linear search is too slow to be used with large lists due to its o(n) average case performance. On the other hand, binary search is considered to be a more efficient method that could be used with large lists. But implementing the binary search could be quite tricky and a study has shown that the accurate code for binary search could be found in only five out of twenty books.