Go语言 二分查找算法的实现

二分查找也称折半查找(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]