如果在进行二分搜索时 log2(len(list)) 不是整数，会发生什么？需要进行多少次操作？
我试图弄清楚，如果给定一个数组，而该数组的长度在以 2 为基数“记录”时不会产生整数，那么二分搜索需要执行多少次操作。
我真的不知道该怎么办。
I'm trying to figure out how many operations binary search would have to do if it were given an array whose's length when "logged" with base 2 would not result in a whole number.
I don't really know what to do.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
上限为直接上级整数。你不能做“0.2”操作，它是一或零，你需要做“更多的事情”......所以是一个完整的操作。
对于 5 个元素的数组，二分查找是（最坏情况）：
如您所见，您得到的操作数与 8 个元素（2 的下一个幂）的最坏情况完全相同。
log2(5)=2.32...，上限为 3，这也是最坏的情况。Ceiled to the immediate superior integer. You can't do "0.2" operations, it's one or zero, and you need to do "something more"... So a whole operation.
For an array of 5 elements, your binary search is (worst case):
As you see, you get exactly the same number of operations that a worst case for 8 elements, the next power of two. And
log2(5)=2.32..., ceiled to 3, and that's what the worst case shown too.二分查找中存在三种情况：主元匹配、太大或太小。如果列表的长度为 n，并且枢轴位于索引下限 (n/2)，则新问题的大小为 0、下限 ((n-1)/2)、上限 ((n-1)/2)。
最坏的情况是每次都选择 ceil((n-1)/2) 情况。这给出了大小为 n 的列表的最坏情况比较次数的递推关系：
稍加思考就会发现 C(n) 是 n 的二进制数字长度，
当 n>0 时，floor(log_2(n)) + 1。
There's three cases in binary search: the pivot matches, it's too large, or it's too small. If your list is length n, and the pivot is at index floor(n/2), the new problem has size 0, floor((n-1)/2), ceil((n-1)/2).
The worst-case is when you choose the ceil((n-1)/2) case each time. This gives the recurrence relation for the worst-case number of comparisons for a list of size n as:
A moment's thought shows that C(n) is the length of n in binary digits,
which for n>0 is floor(log_2(n)) + 1.