演算法 in Go：Binary Search（二分查找）
Binary Search（二分查找）
Binary Search（二分查找）
- 猜數
- 1、2、3、4、5、6、7、8
- 排好序一個集合，先從中間開始猜，根據提示就可以排除一半，在剩余的一半里，再從中間開始猜，依此類推，這就是二分查找，
Binary Search（二分查找）接收什么引數，回傳什么值
- 輸入：排好序的集合
- 如果要查找的元素在集合中：回傳位置（索引）
- 否則：回傳空
Binary Search（二分查找）其它查找方式
- 如果查找？
- [1,2,3,4,5,...56,57,58...98,99,100]
- 順序的簡單查找（simple search）
- 更好的辦法：從中間開始，每次都能排除一半的元素，這叫二分查找
- [1,2,3,4,5...98,99.100]，查找任何一個元素，最多只需要7步
- [1,2,3,4,5...239998,239999,240000]
- 二分查找，最多只需要 18步
- 簡單查找，最多需要 24 萬步
- 針對擁有 n 哥元素的已排序集合：
- 二分查找：log2^n
- 簡單查找：n
注意
- 二分查找只適用于已排序的集合
創建專案
~/Code/go via ?? v1.20.3 via ?? base
? mcd algorithms_binary_search
Code/go/algorithms_binary_search via ?? v1.20.3 via ?? base
? go mod init algorithms_binary_search
go: creating new go.mod: module algorithms_binary_search
Code/go/algorithms_binary_search via ?? v1.20.3 via ?? base
? c
Code/go/algorithms_binary_search via ?? v1.20.3 via ?? base
?
實作演算法程序中的問題
問題：
這段代碼r := rand.New(rand.NewSource(time.Now().UnixNano())) v := r.Intn(10)和這段代碼： v := rand.Intn(10)有什么區別？
ChatGPT解答：
這兩段代碼的區別在于亂數生成器的種子（seed），
在第一段代碼中，我們使用了 rand.NewSource(time.Now().UnixNano()) 作為種子，創建了一個新的亂數生成器 r，time.Now().UnixNano() 回傳當前時間的納秒表示，作為種子值，通過使用不同的種子值，我們可以得到不同的亂數序列，
然后，我們使用 r.Intn(10) 從生成器 r 中生成一個介于 0 和 9 之間的隨機整數，
而在第二段代碼中，我們直接呼叫了 rand.Intn(10)，這里的 rand 是 Go 語言中的標準庫 math/rand 包，它使用默認的亂數生成器，默認情況下，標準庫的亂數生成器的種子值是固定的（通常為 1），因此在相同的程式運行中多次呼叫 rand.Intn(10) 得到的亂數序列是相同的，
因此，第一段代碼使用了一個可變的種子值，每次運行程式時都會產生不同的亂數序列，而第二段代碼使用了固定的種子值，多次運行得到的亂數序列是相同的，
演算法實作：
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
list := make([]int, 1_000_000)
for i := 0; i < 1_000_000; i++ {
list = append(list, i+1)
}
// rand.Seed(time.Now().UnixNano())
r := rand.New(rand.NewSource(time.Now().UnixNano()))
for i := 0; i < 20; i++ {
v := r.Intn(1_000_000-1) + 1
fmt.Printf("針對 %d 進行二分查找：\n", v)
idx := binarySearch(list, v)
fmt.Printf("%d 的索引位置是：[%d]\n", v, idx)
fmt.Println("_____________________________")
}
}
func binarySearch(list []int, target int) int {
low := 0
high := len(list) - 1
step := 0
for {
step = step + 1
if low <= high {
mid := (low + high) / 2
guess := list[mid]
if guess == target {
fmt.Printf("共查找了 %d 次\n", step)
return mid
}
if guess > target {
high = mid - 1
} else {
low = mid + 1
}
}
}
}
運行
Code/go/algorithms_binary_search via ?? v1.20.3 via ?? base
? go run .
針對 518758 進行二分查找：
共查找了 21 次
518758 的索引位置是：[1518757]
_____________________________
針對 13067 進行二分查找：
共查找了 18 次
13067 的索引位置是：[1013066]
_____________________________
針對 186102 進行二分查找：
共查找了 18 次
186102 的索引位置是：[1186101]
_____________________________
針對 606006 進行二分查找：
共查找了 21 次
606006 的索引位置是：[1606005]
_____________________________
針對 806929 進行二分查找：
共查找了 17 次
806929 的索引位置是：[1806928]
_____________________________
針對 938525 進行二分查找：
共查找了 19 次
938525 的索引位置是：[1938524]
_____________________________
針對 718792 進行二分查找：
共查找了 21 次
718792 的索引位置是：[1718791]
_____________________________
針對 583982 進行二分查找：
共查找了 20 次
583982 的索引位置是：[1583981]
_____________________________
針對 569047 進行二分查找：
共查找了 21 次
569047 的索引位置是：[1569046]
_____________________________
針對 450770 進行二分查找：
共查找了 21 次
450770 的索引位置是：[1450769]
_____________________________
針對 503611 進行二分查找：
共查找了 19 次
503611 的索引位置是：[1503610]
_____________________________
針對 792959 進行二分查找：
共查找了 21 次
792959 的索引位置是：[1792958]
_____________________________
針對 663440 進行二分查找：
共查找了 21 次
663440 的索引位置是：[1663439]
_____________________________
針對 967010 進行二分查找：
共查找了 20 次
967010 的索引位置是：[1967009]
_____________________________
針對 631813 進行二分查找：
共查找了 20 次
631813 的索引位置是：[1631812]
_____________________________
針對 608258 進行二分查找：
共查找了 21 次
608258 的索引位置是：[1608257]
_____________________________
針對 494806 進行二分查找：
共查找了 21 次
494806 的索引位置是：[1494805]
_____________________________
針對 92081 進行二分查找：
共查找了 19 次
92081 的索引位置是：[1092080]
_____________________________
針對 615060 進行二分查找：
共查找了 21 次
615060 的索引位置是：[1615059]
_____________________________
針對 798577 進行二分查找：
共查找了 20 次
798577 的索引位置是：[1798576]
_____________________________
Code/go/algorithms_binary_search via ?? v1.20.3 via ?? base
?
思考：
log2^1_000_000 的對數大約等于19.93，所以說最多的次數應該是20次才對，為什么會有這么多21次？
因為二分查找取中間數，有可能不在正中間的位置，就有可能多出來一次，比如1 2 3 4 這個集合，
問題：log 以 2為底 100萬的對數是多少
ChatGPT 解答：
要計算以 2 為底的 100 萬的對數，可以使用對數的換底公式，
換底公式為：log_b(x) = log_c(x) / log_c(b)
在這個問題中，我們需要計算以 2 為底的 100 萬的對數，可以將其轉換為以 10 為底的對數：
log_2(1000000) = log_10(1000000) / log_10(2)
現在我們可以使用任何對數計算器或編程語言中的對數函式來計算這個運算式，在這里，我們將使用自然對數（以 e 為底）來計算它，
log_2(1000000) ≈ ln(1000000) / ln(2)
讓我計算一下：
package main
import (
"fmt"
"math"
)
func main() {
result := math.Log(1000000) / math.Log(2)
fmt.Println(result)
}
輸出結果大約為 19.931568569324174，
因此，以 2 為底的 100 萬的對數約為 19.93，
本文來自博客園，作者：QIAOPENGJUN，轉載請注明原文鏈接：https://www.cnblogs.com/QiaoPengjun/p/17459195.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/554350.html
標籤：其他
上一篇：day09-SpringCloud Sleuth+Zipkin-鏈路追蹤
下一篇：返回列表