javascript - 找到二进制搜索结果的最左重复项

Question

假设我有一个包含大量重复项的有序数组:

var array = [ 1, 1, 1, 1, 1,
              2, 2, 2, 2, 2,
              3, 3, 3, 3, 3,
              4, 4, 4, 4, 4,
              5, 5, 5, 5, 5, ];

我也有代码对排序数组中最接近值的索引执行二进制搜索:

function binaryClosestIndexOf(array, value) {
  var mid,
    lo = 0,
    hi = array.length - 1;

  while (hi - lo > 1) {
    mid = (lo + hi) >>> 1;

    if (array[mid] > value)
      hi = mid;
    else
      lo = mid;
  }

  if (value - array[lo] <= array[hi] - value)
    return lo;
  else 
    return hi;
}

执行一些示例搜索可以揭示我的问题:

binaryClosestIndexOf(array, 3.5);
> 14 // array[14] = 3
binaryClosestIndexOf(array, 3.50001);
> 15 // array[15] = 4
binaryClosestIndexOf(array, 3.9);
> 15 // array[15] = 4
binaryClosestIndexOf(array, 4);
> 19 // array[19] = 4
binaryClosestIndexOf(array, 4.49999);
> 19 // array[19] = 4

正如我们所见，该算法没有问题，它确实返回了最接近的值。但它会返回一个有趣的索引组合，从最左到最右。

我想得到最左边的重复索引。我可以在二进制搜索之后引入一个 O(n) 搜索，迭代数组中的每个值，直到找到一个小于当前值的值。我不想这样做。

有没有一种方法可以优雅地执行二分查找，最终得到最左边的重复值？最正确值的算法也可加分!

Answer 1

作为二进制搜索，如果您搜索一个确切的值，您不会被 promise 任何位置(最右或最左)，它可能在中间。

由于二分搜索的工作原理是有一个排序列表，并且减少了两个因素，因此找到边缘索引可能很困难。

我可以想到两种方法

1. 之后使用一个循环，我认为您可以使用随机性使其达到预期的 O(log(n))，因为您可以说最终循环的预期常数时间为 O(1)。
2. 对最接近该数字减去 0.000001 的索引使用第二次二进制搜索(一旦您知道该值)(在您的列表 4 种情况下，这将始终导致第二次运行搜索 3.99999，这将产生 15。注意:您应该检查数字 (3.999999) 是否在列表中并向右移动一个位置以获得您的值，除非您可以确保列表中有一定程度的舍入。这将是 2*log(n) 或 O(log(n )).

如果您的列表很长，我认为选项 2 的预期运行时间实际上会比选项 1 长，因为 2*log(n) 将 > log(n) + 一个常数，除非您知道会有很多重复。