What is the difference between linear search and binary search?

Answer 1

A linear search looks for an item in a list by iterating through it sequentially. Meaning that it looks at the first item, then the second item, then the third item, then the fourth and etc...

Because it is possible that the item you are looking for is the very last item in the list, a linear search runs in O(n) time. For a *randomly* ordered list, the search will run on average in n/2 time.

A binary search is a much more efficient algorithm which can only be used on a SORTED list. A binary search is conceptually equivalent to treating the list as a binary search tree. Because the depth of a balanced binary search tree is log n, a binary search algorithm runs in O(log n) time.

Instead of starting at the beginning of the list, a binary search starts in the middle of the sorted list. If the item it is looking for is less than the item in the middle of the list, then you look in the middle of the half of the list which is less than the middle item. If the item it is looking for is greater than the middle item, then it looks in the middle of the half of the list which is greater than the middle item. This process repeats until you either find what you are looking for, or the size of the sublist that you are looking in is zero.

Answer 2

Linear search is used whenever data is unsorted. You start at the beginning of the sequence and work your way through to the end or until you locate the value your are looking for. The time taken to traverse the entire sequence is therefore a function of the number of items in the sequence, n, such that the best case is constant time, O(1), when the item is at the start of the sequence, and the worst case is O(n) if the item is the final item or doesn't exist. The average case is O(n/2).

Binary search is used whenever the data is in sorted order. Rather than start at the beginning of the sequence you start at the middle. If that's your item then you're done and this represents the best case O(1). If not, then you compare the items. If the item you're looking for is smaller then it must reside in the elements that come before the middle element, which means you can exclude everything that comes after. Conversely, if it is larger it must reside in the elements that come after the middle element, so you can ignore everything that came before. You've now reduced the problem by half. You then repeat the process with the remaining half, and continue reducing the problem by half until the value is found or the remaining half has no more elements. The worst case is then O(log n), which is logarithmic time. Binary search is an example of a divide and conquer algorithm.

Binary search is best performed on sorted arrays. You can also use binary trees to achieve the same thing but these tend to be slower due to then additional overhead of dereferencing nodes. However, when reading unsorted data linearly (sequentially), building a binary tree is the quickest way to sort the elements. Once you have the tree, you can extract nodes one a time using depth-first traversal and thus construct a sorted array.