algorithm - Algorithmic complexity: why does ordering reduce complexity to O(log n)

Question

I'm reading some texts about algorithmic complexity (and I'm planning to take an algorithms course later), but I don't understand the following.

Say I've to search for an item in an unordered list, the number of steps it takes to find it would be proportional to the number of items on that list. Finding it in a list of 10 items could take 10 steps, doing the same for a list of 100000 items could take 100000 steps. So the algorithmic complexity would be linear, denoted by 'O(n)'.

Now, this text[1] tells me if I were to sort the list by some property, say a social security number, the algorithmic complexity of finding an item would be reduced to O(log n), which is a lot faster, off course. Now I can see this happening in case of a b-tree, but how does this apply to a list? Do I misunderstand the text, since English isn't my native language?

[1]http://msdn.microsoft.com/en-us/library/ms379571.aspx

Answer 1

这适用于任何可随机访问的容器。在列表的情况下，您将首先转到中间元素。假设这不是目标，排序会告诉您目标是在上子列表中还是在下子列表中。这本质上变成了二分搜索，与通过 b-tree 搜索没有什么不同。

Answer 2

二进制搜索，检查中间，如果目标较高，则必须位于右侧，如果较小，则位于中间数，依此类推。每次您将列表一分为二时，您都会得到 O(log n)