Scala实现二分查找的代码实例

小肥貓公寓

Scala实现二分查找的代码实例

前提：二分查找的前提是数组内的元素必须是有序的

思想：找到数组的中间值，和需要查找的值进行对比：如果中间值等于查找值，直接返回中间值下标；如果中间值大于查找值，则递归向左边查找；如果中间值小于查找值，则递归向右边查找，直到找完所有的元素 递归的结束条件——数组的开始下标 > 结束下标

扩展：如果一个数组中有多个查找值，需要返回一个元素值等于查找值的下标的数组，在查到第一个元素等于查找值后，分别向前和向后继续扫描（whilt(true)）查找，如果找到将下标放到结果数组内，找不到结束扫描

代码实现（scala）：

object BinarySearch {
    def main(args: Array[String]): Unit = {
        val arr = Array(1,3,4,6,8,11,15,36)
        val result = binarySearch(arr,0,arr.length-1,30)
        if(result.lenth == 0){
            println("没有找到")
        }else{
           for(index<-result){
                 println("下标为： " + index)
        }
    }

    /**
      *
      * @param arr      查询的数组
      * @param left     开始下标
      * @param right    结束下标
      * @param findVal  查找的值
      * @return
      */
    //如果查找值在数组中有多个，需要返回一个对应下标的数组
def binarySearch(arr: Array[Int], left: Int, right: Int, findVal: Int): ArrayBuffer[Int] = {
    //当起始下标大于结束下标时，递归结束
    if (left > right) {
        return ArrayBuffer()
    }
    //找到中间下标
    var mid = (left + right) / 2
    //如果查找值小于中间值，向左递归查找
    if (findVal < arr(mid)) {
        binarySearch(arr, left, mid - 1, findVal)
        //如果查找值大于中间值，向左递归查找
    } else if (findVal > arr(mid)) {
        binarySearch(arr, mid + 1, right, findVal)
        //如果查找值等于中间值，直接返回中间值下标
    } else {
        //定义一个可变数组，用来存储多个查找值的下标的结果
        val resArr = ArrayBuffer[Int]()
        //向左边扫描
        //定义一个变量tmp，它的值比mid要小1
        var tmp = mid - 1
        breakable {
            while (true) {
                //如果数组中tmp下标的数不为查找值或者tmp<0，结束左边扫描
                if (tmp < 0 || arr(tmp) != findVal) {
                    break()
                }
                //如果对象tmp下标的值等于查找值，将这个下标加入结果数组
                if (arr(tmp) == findVal) {
                    resArr.append(tmp)
                }
                //继续向左边查找，直到找不到
                tmp -= 1
            }
        }
        //把mid添加导结果数组中
        resArr.append(mid)
        //向右边扫描
        tmp = mid + 1
        breakable {
            while (true) {
                if (tmp > arr.length - 1 || arr(tmp) != findVal) {
                    break()
                }
                if (arr(tmp) == findVal) {
                    resArr.append(tmp)
                }
                //继续向右边查找，直到找不到
                tmp += 1
            }
        }
        resArr
    }
}
}

到此这篇关于Scala实现二分查找的代码实例的文章就介绍到这了,更多相关Scala二分查找内容请搜索琼殿技术社区以前的文章或继续浏览下面的相关文章希望大家以后多多支持琼殿技术社区！

您可能感兴趣的文章:

• Scala排序算法之归并排序解析
• Scala基础语法总结
• 关于TensorBoard可视化不显示数据问题No scalar data was found
• IntelliJ IDEA基于Scala实现Git检查工具
• Scala中如何中断循环详解
• Python 二分查找之bisect库的使用详解
• C语言通过二分查找实现猜数字游戏
• 详解Go语言实现线性查找算法和二分查找算法
• Java二分查找算法实例详解