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

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

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

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

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

Answer 1

您可以使用Array.prototype.indexOf()

return array.indexOf(array[value - array[lo] <= array[hi] - value ? lo : hi])

Answer 2

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

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

我可以想到两种方法

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

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

Answer 3

重新排列您的数据结构以保留值、最左边的位置和计数，即保留您的数组

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, ];

类似于

var array=[{"v": 1, "l": 0, "c": 5},
           {"v": 2, "l": 5, "c": 5},
           {"v": 3, "l": 10, "c": 5},
           {"v": 4, "l": 15, "c": 5},
           {"v": 5, "l": 20, "c": 5}];

其中 "v" 代表 "value"，"l" 代表 "leftmost index"，"c" 代表 "count"。对值执行二进制搜索，然后 "l" 是最左边的索引， "l" + "c" - 1 是最右边的索引。

如果你编一个约定，你可以把替代结构缩短一点，而不是{"v": 1, "l": 0, "c": 5}，使用[1, 0, 5] 其中对应的项分别是值，最左边的索引和计数。

vararray=[[1, 0, 5],
          [2, 5, 5],
          [3, 10, 5],
          [4, 15, 5],
          [5, 20, 5]];

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

Find leftest duplicate of binary search result

javascript

arrays

algorithm

binary-search