优化排序列表中的查找

Question

我遇到了一个问题，我们得到了一个排序的数字列表，在某些时候列表中的数字开始重复，类似于 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))

可能有递归的方法，但我想不通
有没有更有效的方法来解决这个问题？

Answer 1

您的解决方案具有 O(log N) 的复杂性。似乎没有比这里的二进制搜索更快的算法。所以你的解决方案没问题

Answer 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))

请注意，这还修复了您的实施中的一个错误。我添加了一个测试用例，当第一个元素等于最大值时，你给出了错误的答案。

Answer 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) 元素，线性时间

优化排序列表中的查找

Optimizing find on sorted list

language-agnostic

optimization

recursion

divide-and-conquer