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

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

  1. 数组有序分布(必备条件)。
  2. 数组不频繁增删。
  3. 数组元素值较多(元素值少,顺序查找更快捷方便)。

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

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

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

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

友情链接更多精彩内容