【go语言】递归调用和非递归调用实现二分查找

在编程中，二分查找可以说是一个非常经典的算法。
然而二分查找也并不是万能的，二分查找只有在以下这三种情况下比较实用：

数组有序分布（必备条件）。
数组不频繁增删。
数组元素值较多（元素值少，顺序查找更快捷方便）。

下面我会列出两种实现二分查找的方法。

for循环版本

// 二分查找for循环版本
func binaryFind01(findVal int, arr *[8]int) {
    leftIndex := 0
    rightIndex := len(arr) - 1

    for {
        if leftIndex > rightIndex {  // 关键点：退出条件
            fmt.Println("找不到")
            break
        }
        middleIndex := (leftIndex + rightIndex) / 2
        if (*arr)[middleIndex] == findVal{
            fmt.Println("找到了数值，下标为", middleIndex)
            break
        } else if (*arr)[middleIndex] > findVal { 
            rightIndex = middleIndex - 1   // 关键点：+1/-1的变化
        } else if (*arr)[middleIndex] < findVal {
            leftIndex = middleIndex + 1
        }
    }
}

递归调用版本

// 二分查找递归调用
func BinaryFind02(arr *[8]int, leftIndex int, rightIndex int, findVal int) {
    // 退出条件，判断条件不能为等号，因为在相等时仍然要进行一次判断。
    // 退出条件为等号可能会造成明明数组中有该值，却错过判断的情况发生。
    if leftIndex > rightIndex {
        fmt.Println("没找到")
        return
    }
    
    middleIndex := (leftIndex + rightIndex) / 2
    if  findVal > (*arr)[middleIndex] {
        // 倘若不对middleIndex进行+1/-1的操作，函数有可能陷入死循环
        BinaryFind02(arr, middleIndex + 1, rightIndex, findVal)
    } else if findVal < (*arr)[middleIndex] {
        BinaryFind02(arr, leftIndex, middleIndex - 1, findVal)
    } else {
        fmt.Println("找到了！下标为：", middleIndex)
    }
}

错误分析（代码没出错的读者可自行跳过下文）：

在二分查找中，退出条件和递归调用时新的leftIndex以及rightIndex是非常容易出错的地方，需要格外注意。

1.如果退出条件改为leftIndex == rightIndex或者leftIndex +1 == rightIndex，那么函数可能会提前退出，并造成漏判断的情况发生。

例：如果有一个数组只有三个元素[1,3,5]，当我们想判断1是否在该数组中时，由于退出条件错误，最终将会得到1不在数组中的错误结论。

2.如果在递归调用时，middleIndex没有进行+1/-1的操作，那么函数可能会陷入死循环。

例：一个数组只有三个元素[1,3,5]，当我们想判断2是否在该数组中时，leftIndex永远是0，rightIndex永远是1，函数陷入死循环。

原创不易，转载请标明出处。