若计算机超高速且内存无限，Linear与Binary search哪种更适用？

Hey, great question! When we imagine a computer with infinite speed and memory, it's easy to think algorithm performance goes out the window—but the core constraints and tradeoffs between these two search methods still matter a lot. Let's break this down:

First, the Non-Negotiable Requirement: Sorted Data #

• Binary search only works on sorted datasets. No matter how fast your machine is, if your data is unordered, binary search is useless. Its entire logic relies on comparing the target to the middle element to narrow the search range—something that doesn't make sense with random, unsorted data.
• Linear search has no such restriction. It just scans every element from start to finish, so it works whether your data is sorted, jumbled, or anything in between.

Performance: Even Infinite Speed Can't Skip Logical Steps #

While infinite processing speed means every operation is instant, we still have to look at the number of logical steps each algorithm requires:

• Linear search in the worst case (target is last element or doesn't exist) needs n steps (one for each element). Even if each step takes 0 time, it's still traversing every element logically.
• Binary search's worst case is log₂(n) steps—way fewer. But here's the catch: if your data is unsorted, you have to sort it first to use binary search. Sorting takes n log n steps. For a single search, that's way more overhead than just doing a linear search. But if you're doing multiple searches on the same dataset, sorting once and then using binary search every time becomes way more efficient.

Can You Just Pick Either One? Absolutely Not #

Here's when to choose each:

• Choose linear search if your data is unsorted and you only need to search once. No need to waste steps sorting first—linear search is straightforward and gets the job done without extra prep.
• Choose binary search if your data is already sorted, or if you'll be searching the same dataset multiple times. The reduced number of logical steps makes it cleaner and more efficient, even if the machine is infinitely fast.
• The only exception is tiny datasets (like 5 elements or less)—here, the difference in steps is negligible, so you can pick either without worrying.

内容的提问来源于stack exchange，提问作者RA Hat