数据结构
网络
关系型数据库
操作系统
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 次查看
