- 已关闭**。此问题需要details or clarity。当前不接受答案。
- 想要改进此问题？**添加详细信息并通过editing this post阐明问题。
2天前关闭。
Improve this question
如果我们假设这个值存在并且是随机的，那么要检查中点多少次才能找到这个值，这是针对一个100万个int的数组。
例如，如果该值不存在，则答案为：每次以1，000，000为底的对数或约20，因为从未找到该值。
如果这个数字确实存在，平均检查中点多少次？它是否仍然接近20，如果是，为什么？
当然，这是一个有序数组，目标值是随机的。
根据评论中的建议，所有值都是唯一的，即没有重复值。
下面是代码：
int binarySearch(int array[], int find, int low, int high) {
while(low <= high) {
int mid = low + (high - low) / 2;
if(array[mid] == find) {
return mid;
} else if(array[mid] < find) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
2条答案
按热度按时间9jyewag01#
如果该数字存在，平均检查中点多少次？
约 * log 2N- 1* 次。
它还会是20吗？如果是，为什么？
否。如果该数字确实存在，则某些迭代将提前结束，从而将不存在的目标平均值减少约 * 至少1*。@Mark Tolonen
大约 * 至少1* 是因为如果数组中的值不是唯一的（OP不能解决的问题），查找所需的步骤会更少。
s3fp2yjn2#
如果这个数字确实存在，平均检查中点多少次？它是否仍然接近20，如果是，为什么？
你的二进制搜索将数组中的值组织成一个二叉树，其中根是你检查的第一个中点。在一个完整的二叉树中，* 一半 * 的节点位于最深的一级，剩下的一半节点位于下一个最深的一级，以此类推。
相等性检查通常比它的价值更昂贵，我建议你这样写你的二分查找：