blocks|key|727254|text|对于二分搜索，T(N)+=+T(N/2)+%2B+O(1)+//递归关系|type|unstyled|depth|inlineStyleRanges|entityRanges|data|727255|应用主定理计算递归关系的运行时复杂度:+T(N)+=+aT(N/b)+%2B+f(N)|727256|这里，a=+1，b=2+=>+log+(以b为底)=1|727257|另外，这里f(N)+=n%5Eclog%5Ek(N)+//k+=0&c=+log+(以b为底)|727258|因此，T(N)+=+O(N%5Ec+log%5E(k%2B1)N)+=+O(log(N))|727259|来源：http://en.wikipedia.org/wiki/Master_theorem|offset|length|727260|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Master_theorem^0|0|0|0|0|0|3|17|0|0^^$0|@$1|2|3|4|5|6|7|V|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|W|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|X|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|Y|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|Z|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|10|8|@]|9|@$L|11|M|12|1|13]]|A|$]]|$1|N|3|-4|5|6|7|14|8|@]|9|@]|A|$]]]|O|$P|$5|Q|R|S|A|$T|U]]]]

For Binary Search,
T(N) = T(N/2) + O(1) // the recurrence relation

Apply Masters Theorem for computing Run time complexity of recurrence relations :
T(N) = aT(N/b) + f(N)

Here, a = 1, b = 2
=> log (a base b) = 1

also, here f(N) = n^c log^k(n) //k = 0 &amp; c = log (a base b)

So, T(N) = O(N^c log^(k+1)N) = O(log(N))

Source : <a href="http://en.wikipedia.org/wiki/Master_theorem">http://en.wikipedia.org/wiki/Master_theorem</a>

blocks|key|727304|text|T(n)=T(n/2)%2B1|type|unstyled|depth|inlineStyleRanges|entityRanges|data|727305|T(n/2)=+T(n/4)%2B1%2B1|727306|将(n/2)的值放在上面，这样T(n)=T(n/4)%2B1%2B1。。。。T(n/2%5Ek)%2B1%2B1%2B1.....%2B1|727307|=T(2%5Ek/2%5Ek)%2B1%2B1....%2B1，最大为k|727308|=T(1)%2Bk|727309|当我们带着2%5Ek=n|727310|K=+log+n|727311|因此时间复杂度为O(log+)|727312|entityMap^0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|S|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|T|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|V|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|W|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|X|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|Y|8|@]|9|@]|A|$]]|$1|P|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]]|Q|$]]

T(n)=T(n/2)+1

T(n/2)= T(n/4)+1+1

Put the value of The(n/2) in above so T(n)=T(n/4)+1+1
.
.
.
.
T(n/2^k)+1+1+1.....+1

=T(2^k/2^k)+1+1....+1 up to k

=T(1)+k

As we taken 2^k=n

K = log n

So Time complexity is O(log n)

blocks|key|510701|text|它不会将搜索时间减半，这不会使它成为log(n)。它以对数的方式减小它。考虑一下这一点。如果您在一个表中有128个条目，并且必须线性搜索您的值，那么平均可能需要64个条目才能找到您的值。这是n/2或线性时间。使用二进制搜索，您可以在每次迭代中消除1/2可能的条目，这样最多只需进行7次比较即可找到您的值(+128的对数基数2是7，或者2的7次方是128)。这就是二进制搜索的威力。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|510702|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

It doesn't half search time, that wouldn't make it log(n). It decreases it logarithmicly. Think about this for a moment. If you had 128 entries in a table and had to search linearly for your value, it would probably take around 64 entries on average to find your value. That's n/2 or linear time. With a binary search, you eliminate 1/2 the possible entries each iteration, such that at most it would only take 7 compares to find your value (log base 2 of 128 is 7 or 2 to the 7 power is 128.) This is the power of binary search.

blocks|key|510763|text|二进制搜索算法的时间复杂度属于O(log+)类。这称为big+O+notation。您应该这样解释:给定大小为n的输入集，函数执行时间的渐近增长不会超过log+n。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|510764|这只是一个正式的数学术语，以便能够证明声明，等等。它有一个非常简单的解释。当n变得非常大时，log+n函数将超出执行该函数所需的时间。“输入集合”的大小n就是列表的长度。|510765|简单地说，二进制搜索在O(log+)中的原因是它在每次迭代中将输入集减半。在相反的情况下更容易思考。在x次迭代中，最大二进制搜索算法可以检查多长的列表？答案是2%5Ex。从这里我们可以看到，对于长度为n的列表，二进制搜索算法平均需要log2+n次迭代。|510766|如果它是O(log2+n)而不是O(log+)，这是因为简单地说-使用大的O记法常量不算数。|510767|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Big_O_notation^0|24|5|R|E|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|T|8|@$9|U|A|V|B|C]]|D|@$9|W|A|X|1|Y]]|E|$]]|$1|F|3|G|5|6|7|Z|8|@]|D|@]|E|$]]|$1|H|3|I|5|6|7|10|8|@]|D|@]|E|$]]|$1|J|3|K|5|6|7|11|8|@]|D|@]|E|$]]|$1|L|3|-4|5|6|7|12|8|@]|D|@]|E|$]]]|M|$N|$5|O|P|Q|E|$R|S]]]]

The time complexity of the binary search algorithm belongs to the O(log n) class. This is called <a href="http://en.wikipedia.org/wiki/Big_O_notation" rel="noreferrer">big O notation</a>. The way you should interpret this is that the asymptotic growth of the time the function takes to execute given an input set of size n will not exceed <code>log n</code>.

This is just formal mathematical lingo in order to be able to prove statements, etc. It has a very straightforward explanation. When n grows very large, the log n function will out-grow the time it takes to execute the function. The size of the "input set", n, is just the length of the list.

Simply put, the reason binary search is in O(log n) is that it halves the input set in each iteration. It's easier to think about it in the reverse situation. On x iterations, how long list can the binary search algorithm at max examine? The answer is 2^x. From this we can see that the reverse is that on average the binary search algorithm needs log2 n iterations for a list of length n.

If why it is O(log n) and not O(log2 n), it's because simply put again - Using the big O notation constants don't count.

blocks|key|510656|text|⌊log₂(n)+%2B+1⌋是在二进制搜索中查找某些内容所需的最大比较次数。平均情况进行大约log₂(n)+-1比较。以下是更多信息：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|510657|http://en.wikipedia.org/wiki/Binary_search#Performance|offset|length|510658|entityMap|0|LINK|mutability|MUTABLE|url^0|0|0|1I|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@$D|O|E|P|1|Q]]|A|$]]|$1|F|3|-4|5|6|7|R|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|C]]]]

⌊log₂(n) + 1⌋ is the maximum number of comparisons that are required to find something in a binary search. The average case makes approximately log₂(n) - 1 comparisons. Here's more info:
<a href="http://en.wikipedia.org/wiki/Binary_search#Performance" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Binary_search#Performance</a>

blocks|key|510990|text|由于我们每次都将一个列表减半，因此我们只需要知道在将列表除以2的过程中我们得到了多少步。在下面给定的计算中，x表示我们划分列表直到得到一个元素的次数(在最坏的情况下)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|510991|1=+N/2x|510992|2x+=N|510993|使用log2|510994|log2(2x)+=+log2(N)|510995|x*log2(2)+=+log2(N)|510996|X=+log2(N)|510997|entityMap^0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|S|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|T|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|U|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|V|8|@]|9|@]|A|$]]|$1|N|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|O|$]]

Since we cut down a list in to half every time therefore we just need to know in how many steps we get 1 as we go on dividing a list by two. In the under given calculation x denotes the numbers of time we divide a list until we get one element(In Worst Case).

1 = N/2x

2x = N

Taking log2

log2(2x) = log2(N) 

x*log2(2) = log2(N)

x = log2(N)

blocks|key|727531|text|T(N)+=+T(N/2)+%2B1|type|unstyled|depth|inlineStyleRanges|entityRanges|data|727532|T(N)+=+T(N/2)+%2B1=+(T(N/4)+%2B+1)%2B+1|727533|..。|727534|T(N)+=+T(N/N)+%2B+(1+%2B1%2B1+%2B...+%2B+1)+=1%2B+logN+(以2为底的对数)=1%2B+logN|727535|因此，二分查找的时间复杂度为O(logN)|727536|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|N|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|O|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|P|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|K|$]]

T(N) = T(N/2) + 1 

T(N) = T(N/2) + 1 = (T(N/4) + 1)+ 1

...

T(N) = T(N/N) + (1 + 1 + 1 +... + 1) = 1 + logN (base 2 log) = 1 + logN

So the time complexity of binary search is O(logN)

blocks|key|727735|text|这是使用主定理的解决方案，带有可读的LaTeX。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|727736|对于二分搜索递归关系中的每个递归，我们将问题转化为一个子问题，运行时间为T(N/2)。因此：|727737|​|727738|📷|atomic|offset|length|727739|727740|代入主定理，我们得到：|727741|727742|727743|727744|现在，因为|727745|727746|是0，而f(n)是1，我们可以使用主定理的第二种情况，因为：|727747|727748|727749|727750|这意味着：|727751|727752|727753|727754|entityMap|0|IMAGE|mutability|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/8e1feafb652e516e1ac79c0665cf7a51.gif|imageAlt|1|https://ask.qcloudimg.com/http-save/yehe-900000/5c2322c8ed2ed54f35a03f7d9f982516.gif|2|https://ask.qcloudimg.com/http-save/yehe-900000/9f935c4761ff249eaa84ce28ad5631da.gif|3|https://ask.qcloudimg.com/http-save/yehe-900000/437af7a4ee6a416e2ec9204e4bc473f8.gif|4|https://ask.qcloudimg.com/http-save/yehe-900000/37f32f9b0fb7e1c93058fc25276c475d.gif^0|0|0|0|0|1|0|0|0|0|0|0|1|1|0|0|0|0|1|2|0|0|0|0|1|3|0|0|0|0|0|1|4|0|0^^$0|@$1|2|3|4|5|6|7|1K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1L|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|1M|8|@]|9|@]|A|$]]|$1|F|3|G|5|H|7|1N|8|@]|9|@$I|1O|J|1P|1|1Q]]|A|$]]|$1|K|3|E|5|6|7|1R|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|1S|8|@]|9|@]|A|$]]|$1|N|3|E|5|6|7|1T|8|@]|9|@]|A|$]]|$1|O|3|G|5|H|7|1U|8|@]|9|@$I|1V|J|1W|1|1X]]|A|$]]|$1|P|3|E|5|6|7|1Y|8|@]|9|@]|A|$]]|$1|Q|3|R|5|6|7|1Z|8|@]|9|@]|A|$]]|$1|S|3|G|5|H|7|20|8|@]|9|@$I|21|J|22|1|23]]|A|$]]|$1|T|3|U|5|6|7|24|8|@]|9|@]|A|$]]|$1|V|3|E|5|6|7|25|8|@]|9|@]|A|$]]|$1|W|3|G|5|H|7|26|8|@]|9|@$I|27|J|28|1|29]]|A|$]]|$1|X|3|E|5|6|7|2A|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|6|7|2B|8|@]|9|@]|A|$]]|$1|10|3|E|5|6|7|2C|8|@]|9|@]|A|$]]|$1|11|3|G|5|H|7|2D|8|@]|9|@$I|2E|J|2F|1|2G]]|A|$]]|$1|12|3|E|5|6|7|2H|8|@]|9|@]|A|$]]|$1|13|3|-4|5|6|7|2I|8|@]|9|@]|A|$]]]|14|$15|$5|16|17|18|A|$19|1A|1B|-4]]|1C|$5|16|17|18|A|$19|1D|1B|-4]]|1E|$5|16|17|18|A|$19|1F|1B|-4]]|1G|$5|16|17|18|A|$19|1H|1B|-4]]|1I|$5|16|17|18|A|$19|1J|1B|-4]]]]

Here is the solution using the master theorem, with readable LaTeX.

For each recurrence in the recurrence relation for binary search, we convert the problem into one subproblem, with runtime T(N/2). Therefore:

<a href="https://i.stack.imgur.com/3Ab0f.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/3Ab0f.gif" alt="T(n) = T(n/2)+1"></a>

Substituting into the master theorem, we get:

<a href="https://i.stack.imgur.com/eBHym.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/eBHym.gif" alt="T(n) = aT(n/b) + f(n)"></a>

Now, because <a href="https://i.stack.imgur.com/VNckf.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/VNckf.gif" alt="logba"></a> is 0 and f(n) is 1, we can use the second case of the master theorem because:

<a href="https://i.stack.imgur.com/gdvEx.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/gdvEx.gif" alt="f(n) = O(1) = O(n0) = O(nlogba)"></a>

This means that:

<a href="https://i.stack.imgur.com/iFhmH.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/iFhmH.gif" alt="T(n)=O(nlogbalogn) = O(n0logn) = O(logn)"></a>

blocks|key|727443|text|ok+see+this
for(i=0;i<n;n=n/2)
{
i%2B%2B;
}
1.+Suppose+at+i=k+the+loop+terminate.+i.e.+the+loop+execute+k+times.

2.+at+each+iteration+n+is+divided+by+half.

2.a+n=n/2+++++++++++++++++++....+AT+I=1
2.b+n=(n/2)/2=n/(2%5E2)
2.c+n=((n/2)/2)/2=n/(2%5E3).......+aT+I=3
2.d+n=(((n/2)/2)/2)/2=n/(2%5E4)

So+at+i=k+,+n=1+which+is+obtain+by+dividing+n++2%5Ek+times
n=2%5Ek
1=n/2%5Ek+
k=log(N)++//base+2|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|727444|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>ok see this
for(i=0;i&lt;n;n=n/2)
{
i++;
}
1. Suppose at i=k the loop terminate. i.e. the loop execute k times.

2. at each iteration n is divided by half.

2.a n=n/2 .... AT I=1
2.b n=(n/2)/2=n/(2^2)
2.c n=((n/2)/2)/2=n/(2^3)....... aT I=3
2.d n=(((n/2)/2)/2)/2=n/(2^4)

So at i=k , n=1 which is obtain by dividing n 2^k times
n=2^k
1=n/2^k 
k=log(N) //base 2
</code></pre>

I heard somebody say that since binary search halves the input required to search hence it is log(n) algorithm. Since I am not from a mathematics background I am not able to relate to it. Can somebody explain it in a little more detail? Does it have to do something with the logarithmic series?

how to calculate binary search complexity

我听到有人说，由于二进制搜索将搜索所需的输入减半，因此它是log(n)算法。因为我没有数学背景，所以我不能与之产生共鸣。有没有人能更详细地解释一下？它一定要和对数级数有关吗？

问如何计算二进制搜索复杂度
EN

回答 9

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何计算二进制搜索复杂度EN

回答 9

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何计算二进制搜索复杂度
EN