二进制搜索最接近的索引/索引到一个带有O（log n）的值

1 回答

• 0

  我想获得与currentTime具有最小dateTime差异的数组的索引/索引

  所以你想找到 largest value less than or equal to currentTime 和 smallest value higher than or equal to 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.
  

  回复于 2024-05-01T15:29:32+08:00