快捷導(dǎo)航

Go語言實(shí)現(xiàn)二分查找方法示例

更新時間：2023年12月22日 11:28:47 作者：低配全棧

這篇文章主要為大家介紹了Go語言實(shí)現(xiàn)二分查找方法示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

使用官方sort包提供search方法快速實(shí)現(xiàn)

對已經(jīng)排好序的數(shù)據(jù), 想快速地找出某一個在對應(yīng)slice的位置索引, 我們可以使用官方sort包提供的search方法快速地實(shí)現(xiàn)二分查找.

官方源碼實(shí)現(xiàn)也非常簡單

func Search(n int, f func(int) bool) int {
  // Define f(-1) == false and f(n) == true.
  // Invariant: f(i-1) == false, f(j) == true.
  i, j := 0, n
  for i < j {
    h := int(uint(i+j) >> 1) // avoid overflow when computing h
    // i ≤ h < j
    if !f(h) {
      i = h + 1 // preserves f(i-1) == false
    } else {
      j = h // preserves f(j) == true
    }
  }
  // i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
  return i
}

sort.Search的作用就是通過二分法, 找到滿足條件的, 即函數(shù)f返回true的數(shù)據(jù)的最小索引, 如果無法找到目標(biāo)值, 則返回參數(shù)n的結(jié)果.

在實(shí)際業(yè)務(wù)中, n一般都是使用查找切片數(shù)據(jù)的長度, 所以在Search方法返回之后, 需要判斷i是否還是目標(biāo)切片的合理索引.

查找第一個大于等于x的索引

func SearchTargetAfter(dataList []int, x int) int {
    return sort.Search(len(dataList), func(i int) bool {
        return dataList[i] >= x
    })
}

查找第一個小于等于x的索引

func SearchTargetBefore(dataList []int, x int) int {
    return sort.Search(len(dataList), func(i int) bool {
        return dataList[i] <= x
    })
}

查找一個確定的數(shù)

那么我就要查找一個確定的數(shù), 我們該怎么做呢?

舉個例子

arrInts := []int{1, 3, 4, 9, 12, 13}
findPos := sort.Search(len(arrInts), func(i int) bool {
  return arrInts[i] == 4
})

結(jié)果輸出, 并不是2, 而是6. 仔細(xì)去看上面的源碼也不難發(fā)現(xiàn), 官方的二分查找的方法, 如果使用了數(shù)值相等來判斷, 就要讓數(shù)據(jù)正好落在每次的二分的位置這樣才能找到, 比如上述的代碼中, 原始的切片數(shù)據(jù)不變的情況下, 如果改為查找的目標(biāo)為9, 那么是可以正確獲取位置的.

因此這里要注意, 如果要查找確定的數(shù)字的目標(biāo)位置, 使用sort.Search方法的時候, func的返回值, 需要使用上述的找到第一個大于等于目標(biāo)索引的位置, 或者小于等于目標(biāo)索引的位置, 得出來索引位置之后, 再去獲取索引值是否跟目標(biāo)數(shù)據(jù)一樣, 來判斷該數(shù)據(jù)是否存在這個數(shù)組中以及它所處的位置.

以上就是Go語言實(shí)現(xiàn)二分查找方法示例的詳細(xì)內(nèi)容，更多關(guān)于Go 二分查找的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: