在一组64个元素中进行二进制搜索需要进行多少次比较？

推荐答案1

假设 n元素 在集合中，遇到搜索元素的一般理解是:

(n/2^k)= 1

(lhs =按2缩小到1元素= rhs所需的分隔数)

=> 2^k = n

应用 log> log> log(base 2) <跨越两侧，我们得到:

=> log(2^k)= log n

=> k = log n

对于您的问题，n =64.

k = log 64

k = log(2^6)

k = 6 log 2

=> k = 6

但是，6是需要比较的平均/最坏情况数.最好的情况可能是1比较，如果搜索元素是首次迭代时中间的搜索元素.

谢谢 阅读.

推荐答案2

这取决于.如果您真的觉得自己必须进行二进制搜索，那么在最坏的情况下，几乎是64或6的日志基础.

问题以您可以一次尝试找到元素而无需使用任何比较的方式.

例如，如果数据键是8位，则可以具有向量有256个元素，其中64个实际上已满.您可以直接索引查看您想要的元素是否存在.

这是哈希的特定情况，也是哈希工作的其他方法.

哈希比二进制搜索要快得多，但不使用太多额外的空间.

推荐答案3

注意 - 二进制搜索仅应用排序，有序的列表.

我们知道，二进制搜索将log n base 2时间搜索特定元素.

如果集合中有n个元素，则选择二进制搜索，然后以log n base 2 time.

1)首先，您检查阵列中有多少个元素.如果您的数组中的元素大于 1，那么您 去下一步.

2)二进制搜索使用分类 平均值=(0+n)/2

3的元素总数的平均值分为两个部分.搜索元素要么大于平均值或较小或等于平均值​​.因此，这个问题分为 n/2和 进行直到搜索完成.

如果您将递归方程式应用于然后，二进制搜索算法然后

t(n)= t(n/2)+1 解决问题

n/2^k = 1

在两个方面登录log(2^k)

log n = k log 2

k = log n base 2.

您还可以使用 迭代 使用while循环或循环进行循环，并在循环中使用均值时，请在每个迭代中进行value时(index index) )是更新.如果您是任何问题，我写了迭代和递归类型的二进制搜索类型的C代码或算法.

现在 > 在这里64元素然后找不到，您可以进行 7比较.您还需要从循环出来的另一个比较.

在最好的情况下，搜索元素的时间为o(1).

谢谢

希望它有帮助.

推荐答案4

t(n)= t(n/2) + o(1)
这是binsearch的重新出现，其中有n个排序的对象.

<如您所见，它与
相似，因为(i = 0; i

简单地说，您的答案是log 64(ie 6)在最坏情况和1个比较中的比较在最好的情况下.

假设:binsearch始终在对象的排序列表上完成

推荐答案5

如果您问需要多少比较才能在有序数组中进行64个元素，则答案是最坏的情况下的7个:一个加上64个二进制日志.

如果您确定要在数组中寻找的内容，答案将是6.