Existence of some search algorithms

Question

The lowest time complexity of search algorithms for sorted lists is $$O(n)=logn$$.

The lowest time complexity of sorting algorithms is $$O(n) = nlogn$$

So in order to be able to use a search algorithm for sorted lists we first must sort the list which takes min of $$nlogn$$ time complexity.Since the brute force search algorithm has a time complexity of just $$n$$ why bother sorting the list to figure out if a element is inside a list since $$n<nlogn$$.What is the use of search algorithms of a sorted list?

Answer 1

Your reasoning is relevant: sorting a list to perform a single search would be foolish.

The general idea of search algorithms is that you spend some time preprocessing the data structure, in such a way that the cost of the subsequent searches is lowered. But of course, the total cost after the desired number of queries should not exceed the cost of the same queries without optimization.

In your example, sorting is worth the effort if you need to perform at least $\Omega(\log n)$ queries.

Answer 2

Naturally, if you want to check once whether an element is in an unsorted list, the O(n) brute force approach is the way to go, right as you say in the question.

The effect of pre-sorting the list occurs when there are many queries. For example, when there is an unsorted list of length $n$, and then $q$ membership checks, the brute force approach takes $O (n q)$, whereas pre-sorting and binary search take $O (n \log n + q \log n)$. When $q = 1$, it is less efficient than brute force. But when $q = n$, it is $O (n \log n)$ versus $O (n^2)$, a pretty significant difference.