50万个有序的数据，使用 O(logN) 算法查找数据， 只需要查找多少次就可以找到数据呢？需要多长时间呢？有办法计算吗？

Question

50万个有序的数据中查找一个key, 使用的是 O(logN) 的算法, 简单来说就是二分查找，在我的理解中O(logN)就是在一颗平衡的二叉树中查找一个数据, 数据结构可能不同，但是形式是一样的，就是把数据分成两份，不断的分成2份

1.那么50W有序的数据使用O(logN)算法查找，如何计算出最坏的情况下，需要查找多少次，才能找到数据？

"我目前知道的O(logN)的理解:
当数据增大n倍时，耗时增大logN倍，log以2为底
当数据增大8倍时:
8 = log(2) ^ 3, 所以数据增大8倍，耗时只增大3倍"

Answer 1

O(logN) = 2^n >= N 那么最坏就需要查找n次
50W = 2^19 = 524288 >= 500000 = 19 最坏需要查找19次

Answer 2

都知道了logN，N不就是50w么，你不回算，打开计算器算下log（50w）

Answer 3

1：查找多少次由你的算法分治决定，公式就是X=log(分治数)(50W)，二分法就是2，以此类推
2:时间公式就是你下面写的，但是每台机器运算时间都不一样，所以只能得到你机器的基础时间，比如用1000个数据运算一次，得出基础时间，后面50W是1000的多少倍就可以代入你上面的公式。

Answer 4

这有什么不能计算的? 随机构造1000个这样的50w个数据, 开始计时, 查找, 记录时间和次数. 最后统计总数据/1000不就是了吗?

Answer 5

1. 数据在录入时是否使用了有序的数据结构，比如使用了红黑树或堆。
2. 如果没有使用有序数据结构，那么是否使用了排序算法。
3. 在排序的基础上进行lgN算法查找，lgN中N增加n倍，那么数学运算就是 nlgN。