資料結構
網路
關係型資料庫
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Go語言實現二分查詢演算法
在程式設計中，要從陣列、連結串列或任何其他資料結構中搜索任何內容，我們有一些搜尋演算法，其中之一就是二分查詢。在二分查詢中，前提是資料必須已排序。在二分查詢中，我們遵循分治法，其中我們透過應用某些條件來劃分資料，然後僅對該資料執行操作。這樣，我們就可以降低時間複雜度。
例如，如果我們有一個元素陣列 {20, 44, 45, 54, 67, 88, 91}，並且我們想找到 44，那麼二分查詢演算法將以以下方式找到該元素。
找到中間元素 54 並將其與要搜尋的元素（即 44）進行比較，因為 54 大於 44，所以我們不會在右側搜尋，而是劃分陣列並向右移動。
現在陣列為 {20, 44, 45}，我們再次與中間元素進行比較，這次中間元素與我們正在搜尋的元素匹配。
演算法
步驟 1：使用 import 關鍵字在頂部匯入所需的包。
步驟 2：然後 main 函式將首先執行。
首先，我們宣告並初始化陣列。
呼叫 binarySearch() 函式透過傳遞陣列、大小和要搜尋的元素作為引數來搜尋元素。
最後，列印結果，說明元素是否存在。
步驟 3.1：在 binarySearch() 函式中
在第一種方法中，我們正在陣列上執行一個 for 迴圈，其中我們有兩個迭代器 left 和 right。
在迴圈內部，我們找到 left 和 right 的中間值，並將元素與索引 m 處的值進行比較。如果值匹配，則返回索引。
如果索引 m 處的值大於我們正在搜尋的值，則我們將 m-1 分配給迭代器 right。
如果索引 m 處的值小於我們正在搜尋的值，則我們將 m 分配給迭代器 left。
最後，如果元素不存在，則返回 -1。
步驟 3.2：在 binarySearch() 函式中
在第二種方法中，該函式是遞迴的。
基本條件是，如果 left 迭代器大於或等於 right 迭代器，則返回 -1。
在遞迴函式內部，我們找到 left 和 right 的中間值，並將元素與索引 m 處的值進行比較。如果值匹配，則返回索引。
如果索引 m 處的值大於我們正在搜尋的值，則我們透過將 m-1 傳遞給迭代器 right 來呼叫 binarySearch() 函式。
如果索引 m 處的值小於我們正在搜尋的值，則我們透過將 m 傳遞給迭代器 left 來呼叫 binarySearch() 函式。
示例 1
在此示例中，我們將使用簡單的 for 迴圈實現二分查詢。在迴圈中，我們將找到索引 right 和 left 之間的中間元素。如果索引 m 處的元素與我們正在搜尋的元素匹配，則我們將返回 m 並停止迭代，否則我們將相應地更新 right 和 left 並繼續迭代。
package main
import "fmt"
// function to print the array with array and
// size of the array as argument
func printArray(array []int, size int) {
for i := 0; i < size; i++ {
fmt.Print(array[i], " ")
}
fmt.Println()
}
// binary search function to find an element in the array
func binarySearch(array []int, size int, toFind int) int {
var left, right, m int
left = 0
right = size
for left < right {
m = (right + left) / 2
if array[m] == toFind {
// if the element at index m is equal to the element we
// are searching then returning m
return m
} else if array[m] > toFind {
//If the element at index m is greater than the element
//We are searching then we are skipping the right side
// of the array
right = m - 1
} else {
//If the element at index m is less than the element
//We are searching then we are skipping the left side
// of the array
left = m
}
}
return -1
}
func main() {
// decalring and initializing the
// array using the shorthand method
array := []int{20, 44, 45, 54, 67, 88, 91}
// decalring and initializing the
// variable using the var keyword
var toSearch int
toSearch = 3
fmt.Println("Golang program to find an element in an array using binary search using for loop.")
fmt.Print("array: ")
printArray(array, 6)
// linear search function passing array and
// variable as a parameter
index := binarySearch(array, 6, toSearch)
if index == -1 {
fmt.Println(toSearch, "is not present in the array.")
} else {
fmt.Println(toSearch, "is present at index", index, "in the array.")
}
}
輸出
Golang program to find an element in an array using binary search recursively. array: 20 44 45 54 67 88 3 is not present in the array.
示例 2
在此示例中，我們將使用遞迴函式實現二分查詢。在遞迴呼叫中，我們將找到索引 right 和 left 之間的中間元素。如果索引 m 處的元素與我們正在搜尋的元素匹配，則我們將返回 m 並停止遞迴呼叫，否則我們將相應地更新 right 和 left 並繼續呼叫函式，直到基本條件匹配。
package main
import "fmt"
// function to print the array with array and
// size of the array as argument
func printArray(array []int, size int) {
for i := 0; i < size; i++ {
fmt.Print(array[i], " ")
}
fmt.Println()
}
// binary search function to find an element in the array
func binarySearch(array []int, left int, right int, toFind int) int {
if left >= right {
// returning -1 if value not present in the array
return -1
}
//Finding a middle index of the current array
m := (right + left) / 2
if array[m] == toFind {
// if the element at index m is equal to the element we
// are searching then returning m
return m
} else if array[m] > toFind {
//If the element at index m is greater than the element
//We are searching then we are skipping the right side
// of the array
return binarySearch(array, left, m, toFind)
} else {
//If the element at index m is less than the element
//We are searching then we are skipping the left side
// of the array
return binarySearch(array, m+1, right, toFind)
}
}
func main() {
// decalring and initializing the
// array using the short hand method
array := []int{20, 44, 45, 54, 67, 88, 91}
// decalring and initializing the
// variable using the var keyword
var toSearch int
toSearch = 44
fmt.Println("Golang program to find an element in an array using binary search recursively.")
fmt.Print("array: ")
printArray(array, 6)
// linear search function passing array and
// variable as a parameter
index := binarySearch(array, 0, 6, toSearch)
if index == -1 {
fmt.Println(toSearch, "is not present in the array.")
} else {
fmt.Println(toSearch, "is present at index", index, "in the array.")
}
}
輸出
Golang program to find an element in an array using binary search using for loop. array: 20 44 45 54 67 88 44 is present at index 1 in the array.
結論
這是在 Go 語言中執行二分查詢的兩種方法。第二種方法有多個函式呼叫，對於具有大量元素的陣列，堆疊將過載。對於簡單的操作執行此操作不是一種合適的程式設計方式，因此執行 for 迴圈的第一種方法將是實現此目標的更有效方法。要了解有關 Go 語言的更多資訊，您可以瀏覽這些教程。
410 次檢視
