Scala带Effect场景下用二分查找实现元素首尾出现位置查询

前置约束确认 #

现有代码签名如下：

case class Sth(index: Long, str: String)

def fetch(n: Long): F[Sth] = ??? // 已实现，返回带Effect的结果
def findFirstAndLast(min: Long, max: Long, str: String): F[(Long, Long)] = ???

数据规则：

• 所有记录按index连续递增，str以连续分组形式存在，同一个str对应的分组有且仅有一个，不会出现同值分组断开后重复出现的情况
• 合法样例：

Sth(1, "a")
Sth(2, "a")
Sth(3, "b")
Sth(4, "b")
Sth(5, "b")
Sth(6, "c")
Sth(7, "d")
Sth(8, "d")

对应调用findFirstAndLast(1, 8, "b")的预期返回为F((3,5))

• 永远不会出现的非法场景：

Sth(1, "a")
Sth(2, "b")
Sth(3, "b")
Sth(4, "a") // a分组重复出现

核心思路 #

因为str分组唯一且连续，整个序列的str值满足分段有序特性，直接用两次二分查找分别定位目标分组的左右边界即可，全程在Effect上下文内执行，不需要拉取全量数据，时间复杂度O(logN)。
二分判断逻辑：

1. 查找左边界（第一个值等于目标str的index）：如果中间位置的str大于等于目标值，向左收缩搜索范围，记录当前中间位置为候选；如果小于目标值，向右收缩搜索范围，最终收敛到左边界
2. 查找右边界（最后一个值等于目标str的index）：如果中间位置的str小于等于目标值，向右收缩搜索范围，记录当前中间位置为候选；如果大于目标值，向左收缩搜索范围，最终收敛到右边界

注意：二分结束后需要校验边界位置的str是否匹配目标值，处理区间内不存在目标str的异常场景。

代码实现 #

只要F类型具备Monad能力（支持flatMap、pure，Cats Effect、ZIO等主流Effect库都满足该约束），就可以直接用以下实现：

import cats.Monad
import cats.syntax.all._

def findFirstAndLast[F[_]: Monad](min: Long, max: Long, target: String): F[(Long, Long)] = {
  // 二分查找左边界
  def searchLeft(low: Long, high: Long, candidate: Long): F[Long] = {
    if (low > high) candidate.pure[F]
    else fetch((low + high) >>> 1).flatMap { midItem =>
      val midIdx = midItem.index
      if (midItem.str >= target) searchLeft(low, midIdx - 1, midIdx)
      else searchLeft(midIdx + 1, high, candidate)
    }
  }

  // 二分查找右边界
  def searchRight(low: Long, high: Long, candidate: Long): F[Long] = {
    if (low > high) candidate.pure[F]
    else fetch((low + high) >>> 1).flatMap { midItem =>
      val midIdx = midItem.index
      if (midItem.str <= target) searchRight(midIdx + 1, high, midIdx)
      else searchRight(low, midIdx - 1, candidate)
    }
  }

  for {
    leftBound <- searchLeft(min, max, -1L)
    rightBound <- searchRight(min, max, -1L)
    boundaryCheck <- fetch(leftBound)
    _ <- if (boundaryCheck.str != target || leftBound > rightBound) {
      Monad[F].raiseError(new NoSuchElementException(s"target $target not exist in range [$min, $max]"))
    } else ().pure[F]
  } yield (leftBound, rightBound)
}

实现说明 #

• 所有逻辑都在F上下文内执行，fetch的副作用被正确保留，不需要手动执行unsafe类操作
• 用无符号右移>>>1计算中间位置，避免long相加溢出
• 最多触发2 * log2(max - min + 1) + 1次fetch调用，性能远高于线性遍历
• 异常分支可以根据业务需求调整，比如返回F[Option[(Long,Long)]]而非直接抛出错误

内容的提问来源于stack exchange，提问作者fr3ak