二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法，但是，二分查找演算法的前提是傳入的序列是有序的（降序或升序），并且有一個目標值，
二分查找的核心思想是將 n 個元素分成大致相等的兩部分，取中間值 a[n/2] 與 x 做比較，如果 x=a[n/2]，則找到 x，演算法中止，如果 x<a[n/2]，則只要在陣列 a 的左半部分繼續搜索 x，如果 x>a[n/2]，則只要在陣列 a 的右半部搜索 x，
二分查找雖然性能比較優秀，但應用場景也比較有限，底層必須依賴陣列，并且還要求資料是有序的，對于較小規模的資料查找，我們直接使用順序遍歷就可以了，二分查找的優勢并不明顯，二分查找更適合處理靜態資料，也就是沒有頻繁插入、洗掉操作的資料，
程式實作：
package main import "fmt" /* 二分查找函式，假設有序陣列的順序是從小到大 */ func BinaryFind(arr *[]int, leftIndex int, rightIndex int, findValue int) { //判斷leftIndex是否大于rightIndex if leftIndex > rightIndex { fmt.Println("未找到") return } //先找到中間的下標 middle := (leftIndex + rightIndex) / 2 if (*arr)[middle] > findValue { fmt.Printf("小于中間 middle：%d, leftIndex： %d rightIndex：%d findValue：%d \n", middle, leftIndex, middle-1, findValue) //要查找的數，范圍應該在leftIndex與 middle-1 之間 BinaryFind(arr, leftIndex, middle-1, findValue) } else if (*arr)[middle] < findValue { fmt.Printf("大于中間 middle：%d, leftIndex： %d rightIndex：%d findValue：%d \n", middle, middle+1, rightIndex, findValue) //要查找的數，范圍應該在middle+1與 rightIndex 之間 BinaryFind(arr, middle+1, rightIndex, findValue) } else { fmt.Printf("找到了，下標為：%v \n", middle) } } func main() { //定義一個陣列 arr := []int{1, 3, 7, 12, 17, 20, 30, 50, 55, 75} BinaryFind(&arr, 0, len(arr)-1, 30) fmt.Println("main arr=", arr) }
執行結果：
大于中間 middle：4, leftIndex： 0 rightIndex：9 findValue：30 小于中間 middle：7, leftIndex： 5 rightIndex：9 findValue：30 大于中間 middle：5, leftIndex： 5 rightIndex：6 findValue：30 找到了，下標為：6 main arr= [1 3 7 12 17 20 30 50 55 75]
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/40868.html
標籤：Go
上一篇：gRPC in ASP.NET Core 3.x -- Protocol Buffer（2）Go語言的例子（下）