javascript - 使用 O(log n) 二进制搜索最接近值的索引/索引

标签 javascript algorithm binary-search

我已经对具有日期时间(以毫秒为单位)的对象数组(可以存在重复项)进行排序,作为对象的成员,我想获得数组的索引/索引,它与当前时间的日期时间差异最小。我想过使用二进制搜索,但它需要 key 存在于数组中。我可以使用简单的 for 循环,但它会是 O(n)

最佳答案

I want to get the index/index's of the array which has the least dateTime difference from currentTime

所以你想找到小于或等于currentTime最大值和大于或等于currentTime最小值>。您的答案必须是其中之一。

对于第一个,你可以这样写你的二分查找:

while left < right:
  m = left + (right - left) / 2
  if array[m] <= target: # using <= here to save the right index 
                         # in store in case the key exists
    left = m + 1
    store = m
  else:
    right = m

运行后,store 将包含低于或等于 target 的最后一个索引。然后你可以检查:

if array[store] == target:
  you found the target exactly
else:
  check array[store] and array[store + 1] (if not out of bounds) and pick the best.

关于javascript - 使用 O(log n) 二进制搜索最接近值的索引/索引,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31790954/

相关文章:

java - 仅使用一种通过索引获取单词的方法在未知大小的词典中查找单词

javascript - 滚动到顶部 jQuery

ruby - 如何从其他间隔构建间隔数组

c - 二分查找与最后一次出现的最接近的匹配

algorithm - 列表的最大后缀

c# - Floyd-Warshall算法如何输出最短路径?

Java 集合 binarySearch 无法正常工作

javascript - 动画正在降低网页的性能

javascript - YouTube 自动播放解决方法?

javascript - 在google maps api中移动一个圆圈