Go语言实现二分查找算法
二分查找是 logN 级别的查找算法,前提是有序序列并且存储在顺序表中,如果存储方式是链表则不能使用。
二分查找的核心思想理解起来非常简单,有点类似分治思想,即每次都通过跟区间中的中间元素对比,将待查找的区间缩小为一半,直到找到要查找的元素,或者区间被缩小为 0,但是二分查找的代码实现比较容易写错,需要着重掌握它的三个容易出错的地方:循环退出条件、mid 的取值,left 和 right 的更新。
二分查找虽然性能比较优秀,但应用场景也比较有限,底层必须依赖数组,并且还要求数据是有序的,对于较小规模的数据查找,我们直接使用顺序遍历就可以了,二分查找的优势并不明显,二分查找更适合处理静态数据,也就是没有频繁插入、删除操作的数据。
3) 如果 LeftIndex > RightIndex,则表示找不到,退出。
二分查找的核心思想理解起来非常简单,有点类似分治思想,即每次都通过跟区间中的中间元素对比,将待查找的区间缩小为一半,直到找到要查找的元素,或者区间被缩小为 0,但是二分查找的代码实现比较容易写错,需要着重掌握它的三个容易出错的地方:循环退出条件、mid 的取值,left 和 right 的更新。
二分查找虽然性能比较优秀,但应用场景也比较有限,底层必须依赖数组,并且还要求数据是有序的,对于较小规模的数据查找,我们直接使用顺序遍历就可以了,二分查找的优势并不明显,二分查找更适合处理静态数据,也就是没有频繁插入、删除操作的数据。
思路:
1) 先找到中间的下标 middle = (leftIndex + RightIndex) /2 ,然后用中间的下标值和 FindVal 比较。
a:如果 arr[middle] > FindVal,那么就向 LeftIndex ~ (midlle-1) 区间找
b:如果 arr[middle] < FindVal,那么就向 middle+1 ~ RightIndex 区间找
c:如果 arr[middle] == FindVal,那么直接返回
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 查找完毕
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) } } func main() { //定义一个数组 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]
所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频