快捷導(dǎo)航

Scala實(shí)現(xiàn)二分查找的代碼實(shí)例

更新時(shí)間：2023年11月14日 09:32:48 作者：哇哈哈水有點(diǎn)甜

這篇文章主要介紹了Scala實(shí)現(xiàn)二分查找的代碼實(shí)例,找到數(shù)組的中間值,和需要查找的值進(jìn)行對(duì)比：如果中間值等于查找值,直接返回中間值下標(biāo)；如果中間值大于查找值,則遞歸向左邊查找；如果中間值小于查找值,則遞歸向右邊查找,直到找完所有的元素,需要的朋友可以參考下

Scala實(shí)現(xiàn)二分查找的代碼實(shí)例

前提：二分查找的前提是數(shù)組內(nèi)的元素必須是有序的

思想：找到數(shù)組的中間值，和需要查找的值進(jìn)行對(duì)比：如果中間值等于查找值，直接返回中間值下標(biāo)；如果中間值大于查找值，則遞歸向左邊查找；如果中間值小于查找值，則遞歸向右邊查找，直到找完所有的元素遞歸的結(jié)束條件——數(shù)組的開始下標(biāo) > 結(jié)束下標(biāo)

擴(kuò)展：如果一個(gè)數(shù)組中有多個(gè)查找值，需要返回一個(gè)元素值等于查找值的下標(biāo)的數(shù)組，在查到第一個(gè)元素等于查找值后，分別向前和向后繼續(xù)掃描（whilt(true)）查找，如果找到將下標(biāo)放到結(jié)果數(shù)組內(nèi)，找不到結(jié)束掃描

代碼實(shí)現(xiàn)（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("下標(biāo)為： " + index)
        }
    }

    /**
      *
      * @param arr      查詢的數(shù)組
      * @param left     開始下標(biāo)
      * @param right    結(jié)束下標(biāo)
      * @param findVal  查找的值
      * @return
      */
    //如果查找值在數(shù)組中有多個(gè)，需要返回一個(gè)對(duì)應(yīng)下標(biāo)的數(shù)組
def binarySearch(arr: Array[Int], left: Int, right: Int, findVal: Int): ArrayBuffer[Int] = {
    //當(dāng)起始下標(biāo)大于結(jié)束下標(biāo)時(shí)，遞歸結(jié)束
    if (left > right) {
        return ArrayBuffer()
    }
    //找到中間下標(biāo)
    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)
        //如果查找值等于中間值，直接返回中間值下標(biāo)
    } else {
        //定義一個(gè)可變數(shù)組，用來存儲(chǔ)多個(gè)查找值的下標(biāo)的結(jié)果
        val resArr = ArrayBuffer[Int]()
        //向左邊掃描
        //定義一個(gè)變量tmp，它的值比mid要小1
        var tmp = mid - 1
        breakable {
            while (true) {
                //如果數(shù)組中tmp下標(biāo)的數(shù)不為查找值或者tmp<0，結(jié)束左邊掃描
                if (tmp < 0 || arr(tmp) != findVal) {
                    break()
                }
                //如果對(duì)象tmp下標(biāo)的值等于查找值，將這個(gè)下標(biāo)加入結(jié)果數(shù)組
                if (arr(tmp) == findVal) {
                    resArr.append(tmp)
                }
                //繼續(xù)向左邊查找，直到找不到
                tmp -= 1
            }
        }
        //把mid添加導(dǎo)結(jié)果數(shù)組中
        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)
                }
                //繼續(xù)向右邊查找，直到找不到
                tmp += 1
            }
        }
        resArr
    }
}
}

到此這篇關(guān)于Scala實(shí)現(xiàn)二分查找的代碼實(shí)例的文章就介紹到這了,更多相關(guān)Scala二分查找內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: