Go语言实现二分查找算法
二分查找的核心思想是将 n 个元素分成大致相等的两部分,取中间值 a[n/2] 与 x 做比较,如果 x=a[n/2],则找到 x,算法中止,如果 x a[n/2],则只要在数组 a 的左半部分继续搜索 x,如果 x a[n/2],则只要在数组 a 的右半部搜索 x。
二分查找虽然性能比较优秀,但应用场景也比较有限,底层必须依赖数组,并且还要求数据是有序的,对于较小规模的数据查找,我们直接使用顺序遍历就可以了,二分查找的优势并不明显,二分查找更适合处理静态数据,也就是没有频繁插入、删除操作的数据。
1) 先找到中间的下标 middle = (leftIndex + RightIndex) /2 ,然后用中间的下标值和需要查找的值( FindVal)比较。
a:如果 arr[middle] FindVal,那么就向 LeftIndex ~ (midlle-1) 区间找
b:如果 arr[middle] FindVal,那么就向 middle+1 ~ RightIndex 区间找
c:如果 arr[middle] == FindVal,那么直接返回
2) 从第一步的 a、b、c 递归执行,直到找到位置。
3) 如果 LeftIndex RightIndex,则表示找不到,退出。
代码/举例:定义一个包含(1, 2, 5, 7, 15, 25, 30, 36, 39, 51, 67, 78, 80, 82, 85, 91, 92, 97)等值的数组,假设说要查找 30 这个值,如果按照循环的查找方法,找到 30 这个值要执行 7 次,那么如果是按照二分查找呢?二分查找的过程如下:
left = 1, right = 18; mid = (1+18)/2 = 9; 51 30
left = 1, right = mid 1 = 8; mid = (1+8)/2 = 4; 15 30
left = mid + 1 = 5, right = 8; mid = (5+8)/2 = 6; 30 = 30 查找完毕
如上所示只需要执行 3 次,大大减少了执行时间,具体代码实现如下所示:
package main import ( fmt //二分查找函数 //假设有序数组的顺序是从小到大(很关键,决定左右方向) func BinaryFind(arr *[]int, leftIndex int, rightIndex int, findVal int) { //判断 leftIndex是否大于rightIndex if leftIndex rightIndex { fmt.Println( 找不到 ) return //先找到 中间的下标 middle := (leftIndex + rightIndex) / 2 if (*arr)[middle] findVal { //要查找的数,范围应该在 leftIndex 到 middle+1 BinaryFind(arr, leftIndex, middle-1, findVal) } else if (*arr)[middle] findVal { //要查找的数,范围应该在 middle+1 到 rightIndex BinaryFind(arr, middle+1, rightIndex, findVal) } else { fmt.Printf( 找到了,下标为:%v /n , middle)
//定义一个数组 arr := []int{1, 2, 5, 7, 15, 25, 30, 36, 39, 51, 67, 78, 80, 82, 85, 91, 92, 97} BinaryFind( arr, 0, len(arr) - 1, 30) fmt.Println( main arr= ,arr) }
执行结果如下所示:
D:/code go run main.go
找到了,下标为:6
main arr= [1 2 5 7 15 25 30 36 39 51 67 78 80 82 85 91 92 97]
23437.html
go相关文章
- Vue3.0实现todolist之跳转路由(常用的push,back,go等方法)
- 如何证明Go函数 传参都是值传递
- 「Go工具箱」go语言csrf库的使用方式和实现原理
- Go 数据结构和算法篇(三):队列
- Go 常见算法面试题篇(二):在 O(1) 时间内删除单链表结点
- [go-kratos-1]Golang微服务框架kratos安装和使用
- Go错误集锦 | 方法接收者的值类型和指针类型
- Go常见错误集锦之函数式选项模式
- 「Go工具箱」一个简单、易用的多错误管理包:go-multierror
- Go-数据库驱动
- Java2023算法面试题java,python,go
- Go语言与Linux:全新的开发环境体验(go语言linux)
- 徒手用Go编写Redis迈向新技术世界的旅程(徒手用go写个redis)
- 用Go语言深入Redis缓存技术(用go写redis)
- 部署Go语言快速连接Oracle实现轻松部署(go连接oracle简单)
- Go语言查询Oracle数据库实战实例(go语言查询oracle)
- Go语言操作Oracle轻松实现数据库编程(go语言访问oracle)
- Go语言快速安装Oracle数据库(go语言安装oracle)
- 数据库探索Go语言与Oracle数据库的结合(go语言中的oracle)
- 程序Go语言调用Oracle数据库驱动程序指南(go oracle驱动)
- GO语言并发编程之互斥锁、读写锁详解