二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,二分查找算法的前提是传入的序列是有序的(降序或升序),并且有一个目标值。
二分查找的核心思想是将 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)比较。
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 次,那么如果是按照二分查找呢?二分查找的过程如下:
如上所示只需要执行 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)
}
}
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)
}
执行结果如下所示: