Go語(yǔ)言實(shí)現(xiàn)二分查找方法示例
使用官方sort包提供search方法快速實(shí)現(xiàn)
對(duì)已經(jīng)排好序的數(shù)據(jù), 想快速地找出某一個(gè)在對(duì)應(yīng)slice的位置索引, 我們可以使用官方sort包提供的search方法快速地實(shí)現(xiàn)二分查找.
官方源碼實(shí)現(xiàn)也非常簡(jiǎ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的作用就是通過(guò)二分法, 找到滿足條件的, 即函數(shù)f返回true的數(shù)據(jù)的最小索引, 如果無(wú)法找到目標(biāo)值, 則返回參數(shù)n的結(jié)果.
在實(shí)際業(yè)務(wù)中, n一般都是使用查找切片數(shù)據(jù)的長(zhǎng)度, 所以在Search方法返回之后, 需要判斷i是否還是目標(biāo)切片的合理索引.
查找第一個(gè)大于等于x的索引
func SearchTargetAfter(dataList []int, x int) int {
return sort.Search(len(dataList), func(i int) bool {
return dataList[i] >= x
})
}查找第一個(gè)小于等于x的索引
func SearchTargetBefore(dataList []int, x int) int {
return sort.Search(len(dataList), func(i int) bool {
return dataList[i] <= x
})
}查找一個(gè)確定的數(shù)
那么我就要查找一個(gè)確定的數(shù), 我們?cè)撛趺醋瞿?
舉個(gè)例子
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ù)值相等來(lái)判斷, 就要讓數(shù)據(jù)正好落在每次的二分的位置這樣才能找到, 比如上述的代碼中, 原始的切片數(shù)據(jù)不變的情況下, 如果改為查找的目標(biāo)為9, 那么是可以正確獲取位置的.
因此這里要注意, 如果要查找確定的數(shù)字的目標(biāo)位置, 使用sort.Search方法的時(shí)候, func的返回值, 需要使用上述的找到第一個(gè)大于等于目標(biāo)索引的位置, 或者小于等于目標(biāo)索引的位置, 得出來(lái)索引位置之后, 再去獲取索引值是否跟目標(biāo)數(shù)據(jù)一樣, 來(lái)判斷該數(shù)據(jù)是否存在這個(gè)數(shù)組中以及它所處的位置.
以上就是Go語(yǔ)言實(shí)現(xiàn)二分查找方法示例的詳細(xì)內(nèi)容，更多關(guān)于Go 二分查找的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
提升Go語(yǔ)言開(kāi)發(fā)效率的小技巧實(shí)例(GO語(yǔ)言語(yǔ)法糖)匯總
這篇文章主要介紹了提升Go語(yǔ)言開(kāi)發(fā)效率的小技巧匯總,也就是Go語(yǔ)言的語(yǔ)法糖，掌握好這些可以提高我們的開(kāi)發(fā)效率，需要的朋友可以參考下2022-11-11
這篇文章主要介紹了Golang中的http.Server源碼，實(shí)現(xiàn)一個(gè)http.Server非常容易，只需要短短幾行代碼，同時(shí)有了協(xié)程的加持，Go實(shí)現(xiàn)的http.Server能夠取得非常優(yōu)秀的性能，下面我們來(lái)分析看看http.Server的源碼2023-05-05
Go語(yǔ)言：打造優(yōu)雅數(shù)據(jù)庫(kù)單元測(cè)試的實(shí)戰(zhàn)指南
Go語(yǔ)言數(shù)據(jù)庫(kù)單元測(cè)試入門：聚焦高效、可靠的數(shù)據(jù)庫(kù)代碼驗(yàn)證！想要確保您的Go應(yīng)用數(shù)據(jù)層堅(jiān)如磐石嗎？本指南將手把手教您如何利用Go進(jìn)行數(shù)據(jù)庫(kù)單元測(cè)試,輕松揪出隱藏的bug,打造無(wú)懈可擊的數(shù)據(jù)處理邏輯,一起來(lái)探索吧！2024-01-01
源碼分析Golang?log是如何實(shí)現(xiàn)的
go語(yǔ)言的log包提供了簡(jiǎn)單的日志記錄功能,允許開(kāi)發(fā)者在應(yīng)用程序中記錄重要的信息、錯(cuò)誤、警告等,log包是Go標(biāo)準(zhǔn)庫(kù)的一部分,因此,使用它不需要安裝額外的第三方庫(kù),本文給大家源碼分析了Golang?log是如何實(shí)現(xiàn)的,需要的朋友可以參考下2024-03-03
golang 后臺(tái)進(jìn)程的啟動(dòng)和停止操作
這篇文章主要介紹了golang 后臺(tái)進(jìn)程的啟動(dòng)和停止操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2021-04-04
Ubuntu安裝Go語(yǔ)言運(yùn)行環(huán)境
由于最近偏愛(ài)Ubuntu，在加上作為一門開(kāi)源語(yǔ)言，在Linux上從源代碼開(kāi)始搭建環(huán)境更讓人覺(jué)得有趣味性。讓我們直接先從Go語(yǔ)言的環(huán)境搭建開(kāi)始2015-04-04
go語(yǔ)言是一種快速、分布式、并發(fā)編程的語(yǔ)言,它天生適合于處理高并發(fā)場(chǎng)景下的消息傳遞和處理,在本文中,我們將介紹Kafka安裝部署+go整合過(guò)程,感興趣的朋友一起看看吧2024-08-08
本文主要介紹了GO語(yǔ)言中接口和接口型函數(shù)的使用，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-03-03
golang 實(shí)現(xiàn)兩個(gè)結(jié)構(gòu)體復(fù)制字段
這篇文章主要介紹了golang 實(shí)現(xiàn)兩個(gè)結(jié)構(gòu)體復(fù)制字段，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2021-04-04
用Go語(yǔ)言標(biāo)準(zhǔn)庫(kù)實(shí)現(xiàn)Web服務(wù)之創(chuàng)建路由
在上一節(jié)中創(chuàng)建了項(xiàng)目，這篇文章主要介紹如何用Go語(yǔ)言標(biāo)準(zhǔn)庫(kù)創(chuàng)建路由，文中有詳細(xì)的代碼示例，對(duì)大家的學(xué)習(xí)或工作有一定的幫助，感興趣的同學(xué)可以參考下2023-05-05