我已经对具有日期时间(以毫秒为单位)的对象数组(可以存在重复项)进行排序,作为对象的成员,我想获得数组的索引/索引,它与当前时间的日期时间差异最小。我想过使用二进制搜索,但它需要 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/