an information-theoretic lower bound
Think of the children's game Twenty Questions. If I am thinking of one item out of a million, each yes/no question you ask can, at best, cut the possibilities in half, so you need at least about log2(1,000,000) = 20 questions to be sure. No strategy can do better, because each question buys you at most one bit of certainty. An information-theoretic lower bound is exactly this idea turned into a proof technique: to single out one answer among many, you must gather enough bits of information, and each cheap operation supplies only a bounded amount.
The recipe has two ingredients. First, count the number of distinct possible answers the algorithm might have to output — call it M. Distinguishing M possibilities requires at least log2(M) bits of information. Second, bound how much information one basic step reveals. In the comparison model a single comparison has three outcomes (<, =, >) but is usually treated as a yes/no with at most one useful bit, so any correct algorithm needs at least log2(M) comparisons in the worst case. That single argument delivers both headline bounds: sorting has M = n! answers, giving log2(n!) = Omega(n log n); searching a sorted array has M = n+1 outcomes, giving log2(n+1) = Omega(log n).
Used carefully, this is a clean and general tool, but it has real limits you must respect. It only bounds the information-gathering steps; if each step can reveal MORE than one bit, the floor drops accordingly — an operation reading a whole machine word leaks many bits, which is exactly why radix sort escapes the n log n barrier. It is also a worst-case, counting style of argument: it shows SOME input needs the work but does not identify which, and it usually gives the right order of magnitude rather than the exact constant. When a single comparison can give more than a bit (a three-way comparison gives up to log2(3) bits), the careful version uses log_3 instead of log_2, which changes constants but not the Omega.
Guessing one of 8 equally likely cards with yes/no questions: you need at least log2(8) = 3 questions, and a halving strategy achieves exactly 3. With 9 cards you need ceil(log2(9)) = 4. The bound log2(M) is the information floor; sorting just plugs in M = n!.
To pick one of M answers, gather log2(M) bits; if each step gives one bit, that many steps are forced.
The argument bounds INFORMATION, not arbitrary work, and assumes each step yields few bits. If an operation reveals many bits (reading a key's digits), the floor falls — which is precisely how radix sort beats the comparison-sorting bound without contradiction.