Binary search vs linear search

Isn't the answer simply O(log N) vs O(N)? Let's back off and check their assumptions first.

To do a binary search, the items have to be sorted, which probably costs you O(N log N), while linear search does not come with such cost.

Secondly, the runtime cost O(log N) or O(N) is for finding a particular item. What happens if you want to add/remove an item to an existing list?

For linear search the insertion costs you O(1), since you do not care about the order. Deletion is O(N) because you need to locate the item first and then with a linked list implementation, it requires setting the pointers properly, which is a constant cost, while with an array implementation, it requires either marking that position as invalid, which will defeat the O(N) in the following operations, or shifting other items following the item you have deleted/inserted, which is O(N).

For binary search, it is tricky. With an array based implementation, both insertion and deletion will cost you O(N) as what we have seen in the linear search. You may do the marking for deletions while it will defeat the O(N) search cost if deletion is frequent. How about using a link list? A solution might come to you quickly is that a link list allows O(1) insertion/deletion once you find the item.But how can you achieve the O(log N) search cost with a linked list? A link list does not give you O(1) random access.

So when insertion/deletion operations are rare and the initial sorting cost is cheap compared to the number of search operations you will perform, binary search is the way to go. When you have a small number of items and the insertion/deletion operations are frequent, linear search does a better job. Similarly, when implementing sorting algorithms such as quick sort, insertion sort is often used when it comes to sorting a small number of items.