0

我最近收到了一个面试问题，说你有一个有序的数字列表（元素的数量可能非常大，大约 100000），你要找到大于给定数字的最小数字，建议如何做到这一点O（log n）时间......我的第一个猜测是使用类似树的数据结构，面试官说是的，但是他们有构建这些树的开销，我是否可以建议另一种方法？我的明显答案是使用数组进行二进制搜索，但我想知道这是否可行，或者是否还有其他方法？

4

1 回答 1

0

这取决于您使用的列表的类型。

如果它不是索引列表，那么 O(logN) 将不可能没有任何重组。

所以如果它是一个索引列表。

您可以按除法搜索。

将目标与 a[n/2] 进行比较

如果 a[n/2] 小于目标 .. 您的搜索空间就会减少。从 a[n/2+1]..a[n-1] 开始

使用相同的方法递归算法，直到找到一对这样 a[i] < target < a[i+1]

那将结束， a[i+1] 是你的答案..!!

于 2013-03-30T23:09:20.843 回答