【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，函数陷入死循环。

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