有人能解释我当谈到二进制的搜索，我们说的运行时间复杂度的 O（log n）的的？我在谷歌搜索，并得到了下面，

Can someone explain me when it comes to "Binary" search we say the running time complexity is O(log n)? I searched it in Google and got the below,

的次数，可以减少一半的搜索空间的数目是相同的日志 2 N

"The number of times that you can halve the search space is the same as log2 n".

我知道我们减半，直到我们找到的数据结构中的搜索关键字，但是为什么我们要考虑它的日志 2 N 的？据我所知，电子 X 是指数增长等等的日志 2 N 的是二进制衰减。但我无法跨preT在我的对数定义的理解方面的二进制搜索。

I know we do halve until we find the search key in the data structure, but why we have to consider it as log2 n? I understand that ex is exponential growth and so the log2 n is the binary decay. But I am unable to interpret the binary search in terms of my logarithm definition understanding.

感谢

推荐答案

认为它是这样的：

如果你能负担得起一半的东​​西的 M 的时候，（例如，你可以花得起时间成正比的 M 的），那么如何大阵你能负担得起搜索？

If you can afford to half something m times, (i.e., you can afford to spend time proportional to m), then how large array can you afford to search?

尺寸显然阵列的 2 M 的，对吧？

Obviously arrays of size 2m, right?

所以，如果你可以搜索大小的数组的 N = 2 M 的，那么花费的时间是成正比的 M 的，解决 M 的的的 N 的是这样的：

So if you can search an array of size n = 2m, then the time it takes is proportional to m, and solving m for n look like this:

N = 2 M

登录 2 （N）=登录 2 （2 M ）

log2(n) = log2(2m)

登录 2 （N）= M 换句话说：大小的阵列上执行二进制搜索的 N = 2 M 的需要时间成正比的 M 的，或者等价地，比例为日志 2 （N）的。

log2(n) = m Put another way: Performing a binary search on an array of size n = 2m takes time proportional to m, or equivalently, proportional to log2(n).