社区微信群开通啦，扫一扫抢先加入社区官方微信群
社区微信群
社区微信群开通啦，扫一扫抢先加入社区官方微信群
社区微信群
二分查找也称折半查找（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]
如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！
