脚本之家

电脑版
提示:原网页已由神马搜索转码, 内容由www.jb51.net提供.
您的位置:首页软件编程Scala→ Scala二分查找

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

  更新时间:2023年11月14日 09:32:48  作者:哇哈哈水有点甜 
这篇文章主要介绍了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基础简介及代码示例,小编觉得挺不错的,这里给大家分享下,供需要的朋友参考。
      2017-10-10
    • 这篇文章主要介绍了Java排序算法之归并排序解析,简介:归并排序是一种经典的排序算法,它采用分治的思想,将待排序的数组不断地分割成小的子数组,然后再将这些子数组合并成有序的数组,需要的朋友可以参考下
      2023-10-10
    • 下面小编就为大家带来一篇浅谈Scala的Class、Object和Apply()方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
      2017-05-05
    • 这篇文章主要介绍了Scala基础语法总结,需要的朋友可以参考下
      2023-10-10
    • 这篇文章主要为大家详细介绍了Scala安装及环境图文配置教程,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
      2018-03-03
    • 这篇文章主要给大家介绍了关于如何利用Gradle构建scala多模块工程的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧。
      2018-04-04
    • 这篇文章主要介绍了Windows7下安装Scala 2.9.2教程,本文给出了Scala的安装步骤以及在Eclipse IDE安装Scala的步骤,需要的朋友可以参考下
      2015-03-03
    • 这篇文章主要介绍了Scala实现二分查找的代码实例,找到数组的中间值,和需要查找的值进行对比:如果中间值等于查找值,直接返回中间值下标;如果中间值大于查找值,则递归向左边查找;如果中间值小于查找值,则递归向右边查找,直到找完所有的元素,需要的朋友可以参考下
      2023-11-11

    最新评论