首页 文章

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

提问于
浏览 次
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, ];

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

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

我们可以看到，算法没有问题，它确实返回最接近的值 . 但它返回了一个有趣的指数混合物，从最左边到最右边 .

I want to get the leftest duplicate index . 我可以在二进制搜索之后引入 O(n) 搜索，迭代遍历数组中的每个值，直到找到小于当前值的值 . 我不想这样做 .

有没有办法优雅地执行二进制搜索，最终得到最左边的重复值？对于最有 Value 的算法，奖励积分也是如此！

javascript arrays algorithm binary-search

3 回答

  • 0

    你可以用 Array.prototype.indexOf()

    return array.indexOf(array[value - array[lo] <= array[hi] - value ? lo : hi])
    回复于
  • 0

    作为二元搜索，如果你搜索一个确切的值，你不会被承诺任何位置（最正确或最左边），它可能在中间 .

    由于二进制搜索通过具有排序列表并且减少两个因子而发现边缘索引可能是困难的 .

    我可以想到两种方法

    • 之后使用循环，我认为你可以使用随机性来预期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）一个常量，除非你知道会有很多重复 .

    回复于
  • 0

    重新排列数据结构以保持值，最左侧位置和计数，即保留阵列

    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”表示“值”，“l”表示“最左侧索引”，“c”表示“计数” . 对值执行二进制搜索，然后“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]];
    回复于

相关问题