二分搜索算法(Scala)

介绍

先按列一下 wiki 解释

在计算机科学中,二分搜索(英语:binary search),也称折半搜索(英语:half-interval search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索演算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

复杂度分析

  • 时间复杂度: 折半搜索每次把搜索区域减少一半
    • 最小时间复杂度$O\left(1\right)$
    • 最大时间复杂度$O\left(\log n\right)$
  • 空间复杂度
    • 非尾递归$O\left(\log n\right)$
    • 尾递归优化或迭代$O\left(1\right)$

实现

BinarySearch.scala

/**
* BinarySearch
*
* @author zhaihao
* @version 1.0 2016/09/12 10:21
* @see [[https://zh.wikipedia.org/wiki/二分搜索算法]]
*/
class BinarySearch extends FunSuite {

def binarySearch(target: Int)(list: List[Int]) = {
@tailrec
def go(low: Int, high: Int): Option[Int] = low + (high - low) / 2 match {
case _ if low > high => None
case mid if list(mid) > target => go(low, mid - 1)
case mid if list(mid) < target => go(mid + 1, high)
case mid => Some(mid)
}

go(0, list.size - 1)
}

test("二分查找") {
val list = (1 to 5).toList
(0 to 6).map(binarySearch(_)(list)).foreach(println)
}
}

需要注意的地方,low + (high - low) / 2 可以避免 (high + low) / 2在高位可能产生溢出的风险。

下面是一个图示

Alt text


- - - - - - - - End Thank For Your Reading - - - - - - - -