假设我有一个由 n 个元素组成的排序数组。我想使用二分搜索在该数组中找到 2 个不同的键 k1 和 k2。
一个基本的解决方案是分别对它们应用二分搜索，就像对 2 个键的两次调用一样，这会将时间复杂度保持在 2(logn)。
我们可以针对不同的 k 个键 k < n 使用任何其他方法来解决这个问题吗？
最佳答案
您完成的每次搜索都可以用于分割输入，以提高效率。例如，假设对应于 k1 的元素位于索引 i1 处。如果 k2 > k1，您可以将第二次搜索限制为 i1..n，否则将其限制为 0..i1。
最好的情况是您的搜索键也已排序，因此每个新搜索都可以从找到最后一个搜索的位置开始。
关于arrays - 使用二分查找在 n 个元素的数组中查找 k 个不同的键，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20559254/