ok see this
for(i=0;i<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
11 回答
Log2（n）是在二进制搜索中查找内容所需的最大搜索次数 . 平均情况涉及log2（n）-1次搜索 . 这里有更多信息：
http://en.wikipedia.org/wiki/Binary_search#Performance
这是一种更加数学化的方式来看待它，虽然并不是很复杂 . IMO比非正式的更清楚：
问题是，你有多少次N除以2，直到你有1？这基本上是说，在你找到它之前做一个二进制搜索（一半元素） . 在一个公式中，这将是这样的：
乘以2x：
现在做log2：
这意味着您可以将日志分为N次，直到您将所有内容分开 . 这意味着您必须将log N（“执行二进制搜索步骤”）分开，直到找到您的元素 .
对于二进制搜索，T（N）= T（N / 2）O（1）//递归关系
应用Masters定理计算递归关系的运行时复杂度：T（N）= aT（N / b）f（N）
这里，a = 1，b = 2 => log（基数b）= 1
此外，这里f（N）= n ^ c log ^ k（n）// k = 0＆c = log（基数b）
所以，T（N）= O（N ^ c log ^（k 1）N）= O（log（N））
资料来源：http://en.wikipedia.org/wiki/Master_theorem
T（n）= T（n / 2）1
T（n / 2）= T（n / 4）1 1
将（n / 2）的值放在上面，使得T（n）= T（n / 4）1 1 . . . . T（n / 2 ^ k）1 1 1 ..... 1
= T（2 ^ k / 2 ^ k）1 1 .... 1到k
= T（1）k
当我们采取2 ^ k = n
K = log n
所以时间复杂度是O（log n）
它没有搜索时间的一半，也不会使它成为log（n） . 它以对数方式降低它 . 对此稍加思考 . 如果表中有128个条目并且必须线性搜索您的值，那么平均可能需要大约64个条目才能找到您的值 . 这是n / 2或线性时间 . 使用二进制搜索，每次迭代消除1/2可能的条目，这样最多只需7次比较就可以找到你的值（128的基数2是7或2到7的幂是128.）这是二进制搜索的力量 .
二进制搜索算法的时间复杂度属于O（log n）类 . 这叫做big O notation . 你应该解释这个问题的方法是，给定一个大小为n的输入集，函数执行时间的渐近增长不会超过
log n.这只是正式的数学术语，以便能够证明陈述等 . 它有一个非常直接的解释 . 当n增长得非常大时，log n函数将超出执行函数所需的时间 . “输入集”的大小n只是列表的长度 .
简单地说，二进制搜索在O（log n）中的原因是它在每次迭代中将输入集减半 . 在相反的情况下，更容易思考它 . 在x次迭代中，二进制搜索算法最多可以检查列表多长时间？答案是2 ^ x . 由此我们可以看出，相反，平均而言，二进制搜索算法需要log2 n次迭代以获得长度为n的列表 .
如果它为O（log n）而不是O（log2 n），那是因为简单地再次放置 - 使用大O符号常量不计算 .
这是wikipedia条目
如果你看一下简单的迭代方法 . 您只需要删除一半要搜索的元素，直到找到所需的元素 .
以下是我们如何提出公式的解释 .
首先说你有N个元素，然后你做的是⌊N/2⌋作为第一次尝试 . 其中N是下限和上限之和 . N的第一个时间值等于（L H），其中L是第一个索引（0），H是您要搜索的列表的最后一个索引 . 如果你很幸运，你试图找到的元素将位于中间[例如 . 你正在列表{16,17,18,19,20}中搜索18，然后你计算⌊（0 4）/2⌋= 2其中0是下界（L - 数组的第一个元素的索引）和4是上限（H - 索引的最后一个元素） . 在上面的情况中，L = 0且H = 4.现在2是您要搜索的元素18的索引 . 答对了！你找到了 .
如果案件是一个不同的阵列{15,16,17,18,19}，但你仍然在寻找18，那么你就不会幸运，你会做第一个N / 2（即⌊（0 4）/ 2 ⌋= 2然后在索引2处实现元素17不是您要查找的数字 . 现在您知道在下次尝试搜索迭代方式时，您不必查找至少一半的数组 . 你的搜索工作减半了 . 所以基本上，每当你试图找到你在之前的尝试中找不到的元素时，你不会搜索之前搜索过的元素列表的一半 .
所以最糟糕的情况就是
直到...你已经完成了搜索，你想要找到的元素在列表的末尾 .
这表明最坏的情况是当你达到N / 2x，其中x是2x = N.
在其他情况下N / 2x其中x是2x <N x的最小值可以是1，这是最好的情况 .
现在从数学上来说最坏的情况是当值的时候
2x = N.
=> log2（2x）= log2（N）
=> x * log2（2）= log2（N）
=> x * 1 = log2（N）
=>更正式⌊log2（N）1⌋
二进制搜索的工作原理是将问题重复分成两半，如下所示（详细信息省略）：
在[4,1,3,8,5]中寻找3的例子
订购商品清单[1,3,4,5,8]
看看中间项目（4），
如果您正在寻找它，请停止
如果它更大，请查看上半部分
如果不是，请看下半场
使用新列表[1,3]重复步骤2，找到3并停止
当您将问题分成2时，这是一个双向搜索 .
搜索只需要log2（n）步骤来查找正确的值 .
如果你想了解算法的复杂性，我会推荐Introduction to Algorithms .
由于我们每次都将列表减少到一半，因此我们只需要知道在将列表除以2时我们得到的步数为1 . 在给定的计算中，x表示我们划分列表直到得到一个元素的时间数（在最坏情况下） .
1 = N / 2x
2x = N.
以log2为例
log2（2x）= log2（N）
x * log2（2）= log2（N）
x = log2（N）
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（基数2 log）= 1 logN
所以二进制搜索的时间复杂度是O（logN）