algorithm - 二进制搜索 ArrayBuffer

Question

因此，我有一个 ArrayBuffer[Signal]，其中每个 Signal 都有一个时间戳(数组按此时间戳排序)。我想进行二进制搜索并返回某个范围内的信号的 Seq[Signal]。现在是用线性搜索来完成的，主要是因为我是Java出身，是Scala的新手。哪种方法最好？

代码如下:

private def getSignalsFromCache(mapId: String, mac: String, startTime: Long, endTime: Long): Seq[Signal] = {

val signals = getCache(VehicleWithMap(mapId, mac))
val result: ArrayBuffer[Signal] = new ArrayBuffer[Signal]()

if (signals.isEmpty) {
  return signals
}

var startIndex: Int = 0
if (startTime > signals.head.timestamp) {

  while (startIndex < signals.size && signals(startIndex).timestamp < startTime) {
    startIndex += 1
  }
}

var finished: Boolean = false
var currentIndex = startIndex
while (!finished && currentIndex < signals.size) {
  val timestamp = signals(currentIndex).timestamp
  if (timestamp > endTime) {
    finished = true
  }
  else {
    result += signals(currentIndex)
  }
  currentIndex += 1
}
result
}

Answer 1

您可以使用 dropWhile & takeWhile .
这样，您就可以保存所有的可变性和迭代。

注意:这仍然是线性的，但它在 Scala 中更实用也更常见。

private def getSignalsFromCache(mapId: String, mac: String, startTime: Long, endTime: Long): Seq[Signal] =
  getCache(VehicleWithMap(mapId, mac)
    .dropWhile(_.timestamp < startTime)
    .takeWhile(_.timestamp <= endTime)
}

(确保首先对其进行测试，您可能需要稍微调整一下条件)。