Linear Search VS Binary Search

Question

For those who are new to these terms:

Linear search looks down a list, one item at a time. E.g. assuming we have an array of size 1000 which contains unsorted, unique numbers, and we want to find a specific key within the entire array:

for (int i = 0; i < 1000; i++)
{
if (array[i] == 39)
{
std::cout << "Found."; break;
}
}

Binary search on the other hand starts in the middle of the entire list. If the data stored is smaller than provided key, the program will continue to search on the right side of the list. Conversely, if the data stored is larger than the provided key, the program will continue searching on the left aide of the list. This operation continues until the data matches the key provided. Binary search requires data to be sorted. E.g.

1, 4, 5, 10, 15, 20, 40, 41, 45, 50, 60, 61, 71

Assuming the key provided is 20. The program would usually take the median of the set/list to begin with binary search. In this case, we start with 40. 40 > 20, hence the program continues searching on the left side. The median between 1 and 40 is 10. Taking 10 < 20, the program continues to search on the right side. Program takes on of the nearest element to the median between 10 to 40 and lands on 20. 20 == 20, the search is complete.

************************************

Now, is linear search necessarily slower than binary search? It is generally agreeable to a certain extent. However, binary search requires sorting algorithms to keep the list sorted prior to it's execution.

What is your opinion on linear search VS binary search, in terms of efficiency?
When should we prefer one over another?

Answer 1

O(n) vs (O(log n) + O(n log n))
O(n) might be slightly quicker, due to the sorting required for a binary search. But with something that is already near-sorted, insertion sort or heap sort are very fast.

I'd say if there's lots of scrambled data that you will never use sorted, then don't bother doing a binary search. If you do however want it sorted at some time you'd might as well follow through and sort it.
After all, Linear search on sorted data is just asking for slower performance.

On the other hand, a linear search may have issues with lots of data.
Perhaps sorting it once initially to allow for a binary search would be better¿ Then for any new element that is added to the array, an insertion can be done.
So if you ever need to do multiple searches, voila, a binary search.
If you won't be doing multiple searches, eh, might as well just linear and forget the initial sorting.

That's my take on it.
Summary-
Binary if:
*Lots of searches on lots of data will be done
*Will use the sorted data
Linear if: Opposite to binary if.

Answer 2

I agree that binary search on a list requires that list to be previously sorted in order to be efficient. IMHO, though, if you expect to perform several searches, you can 'invest' by sorting once the list, and then the subsequent binary searches are (in average) way faster than linear ones.
If we don't talk only about searches, but also insertions and deletions, a plain list might not be the optimal implementation –a binary tree could help.