提问人：Helder Sepulveda 提问时间：4/19/2020 最后编辑：Helder Sepulveda 更新时间：3/30/2021 访问量：86
优化排序列表上的查找
Optimizing find on sorted list
问：
我遇到了一个问题，我们得到了一个排序的数字列表，在某个时候列表中的数字开始重复，
像这样，我们需要检索重复开始的位置。0,1,2,3,4,5,6,7,8,8,8
以下是我采取的方法......
function find(arr) {
let max = arr.length-1
let min = 0
do {
let iter = Math.round((min + max) / 2)
if (arr[max] == arr[iter])
max = iter
else
min = iter
} while (min + 1 < max)
return max
}
arr = [0,1,2,3,4,5,6,7,8,8,8]
console.log(find(arr))
arr = [0,1,2,2,2,2,2,2,2,2,2]
console.log(find(arr))
arr = [0,2,4,6,8,10,10]
console.log(find(arr))可能有一种递归的方法，但我无法弄清楚
有没有更有效的方法来解决这个问题？
答：
-1赞
bobra
4/19/2020
#1
您的解决方案很复杂。这里似乎没有比二进制搜索更快的算法了。所以你的解决方案是可以的O(log N)
评论
0赞
Raymond Chen
4/19/2020
由于有 n 个可能的答案，所以没有比 log n 更好的了（对抗性参数表明，任何复杂度较低的算法都可以被愚弄。
1赞
pjs
4/19/2020
#2
正如 bobra 和 Raymond Chen 所指出的，你不能比 O（log n） 做得更好。但是，您还询问了递归解决方案。给你：
function find(arr, min_idx = 0, max_idx = arr.length - 1) {
if (min_idx >= max_idx)
return max_idx
let guess = Math.floor((min_idx + max_idx) / 2)
if (arr[guess] == arr[max_idx])
return find(arr, min_idx, guess)
return find(arr, guess + 1, max_idx)
}
let arr = [0,1,2,3,4,5,6,7,8,8,8]
console.log(find(arr))
arr = [0,1,2,2,2,2,2,2,2,2,2]
console.log(find(arr))
arr = [2,4,6,8,10,10]
console.log(find(arr))
arr = [10,10,10]
console.log(find(arr))请注意，这也修复了实现中的一个错误。我添加了一个测试用例，当第一个元素等于最大值时，您的测试用例给出了错误的答案。
评论
1赞
Helder Sepulveda
4/19/2020
这就是门票，是的，我知道我们真的不能比对数时间做得更好，但效率不仅与 BigO 有关，还有递归算法的好处，分而治之真的很适合在多处理器中执行
0赞
Helder Sepulveda
5/15/2020
#3
我意识到所有情况都是：
- 顺序只有一个重复
- 不要在第一个元素上重复
- 第一个元素始终为 0
一些具体的例子
[0,1,2,3,4,5,6,7,8,8,8]
[0,1,2,2,2,2,2,2,2,2,2]
[0,2,4,6,8,8,8,8,8,8,8]
[0,3,6,9,9,9,9,9,9,9,9]
最佳解决方案是仅使用 2 个观测元素，线性时间(last/second)
上一个：字母表的排列，最大限度地减少了构建字符串的子序列的数量
下一个：阵列排列算法
评论