Go语言实现二分查找算法-Go语言教程

Go语言实现二分查找算法" title="二分查找算法">二分查找算法

二分查找是 logN 级别的查找算法，前提是有序序列并且存储在顺序表中，如果存储方式是链表则不能使用。

二分查找的核心思想理解起来非常简单，有点类似分治思想，即每次都通过跟区间中的中间元素对比，将待查找的区间缩小为一半，直到找到要查找的元素，或者区间被缩小为 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，那么直接返回

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 
", 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)
}