我有一个排序的 double 数组(实际上是纬度)，它们相对均匀地分布在 -10 到 -43 的范围内。现在，如果我对该列表进行二分搜索，我会得到 O(log N)。
但是，我可以通过搜索进一步优化搜索表，其中有 34 个键(-10 到 -43)，然后可以直接跳转到该数字的起点。
例如:-23.123424 首先查找键 23 并知道所有 -23 值的起止范围。然后我可以从中间进行二分搜索。
我的 Big-O 会是什么样子？
最佳答案
它仍然是 O(log n)。考虑:在整数查找表中查找起始索引需要恒定的时间，因此该部分不会添加任何内容。然后是 O(log n) 进行二分搜索。实际上，它大约需要 log n/34，因为您希望搜索平均小 34 倍的数组(这些值分布在 34 个不同的间隔中，边界从 -43 到 -10)，但不考虑常量乘数-O 符号。
关于big-o - 什么 Big-O 方程描述了我的搜索？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9815828/