scala版本二分查找的实现方式，查找的值数组中不存在则直接返回-1，可直接在电脑上运行。

import scala.collection.immutable object binarySearch { def main(args: Array[String]): Unit = { val seq: immutable.Seq[Int] = 1 to 1000 val array: Array[Int] = seq.toArray println(binarySearch(array, 0, array.length - 1, array(500))) } /** * 二分查找 时间复杂度O(log2n);空间复杂度O(1) * todo 二分查找的前提是这个数组是升序排序的！！！ */ // 下面这个方法的含义，第一个参数是数组引用，第二的参数是开始索引， // 第三个参数是结束索引，第四个参数是要查找的值 def binarySearch(arr: Array[Int], left: Int, right: Int, findVal: Int): Int = { // 如果第二个参数大于第三个参数，参数传入的有问题，直接返回-1 if (left > right) { //递归退出条件，找不到，返回-1 println(left + "-" + right) return -1 } // 如果最后就剩下两个数或一个数时,要查找的数据，不在这两个数中间， // 说明数组中根本就没有这个数，直接返回就行。 if (right - left == 1 | right - left == 0) { if (arr(right) != findVal && arr(left) != findVal) { println(arr(right) + "\t" + findVal + "\t" + arr(left)) return -1 } } // 第二个参数与第三个参数求平均，得到两者中间的索引。 val midIndex = (right - left) / 2 + left // 要查找的值跟中间值相比较 if (findVal < arr(midIndex)) { // 如果要查找的值小于中间值，则向左递归查找 binarySearch(arr, left, midIndex - 1, findVal) } else if (findVal > arr(midIndex)) { // 如果要查找的值大于中间值，则向右递归查找 binarySearch(arr, midIndex + 1, right, findVal) } else { // 查找到，返回下标 midIndex } } }