Kotlin递归二分查找return后函数未退出问题解决方案

核心问题是递归调用的返回值没有被透传：

• 你在二分查找的左右分支中仅调用了binarySearch递归函数，但没有在递归调用前加return关键字。当深层递归命中目标值、执行return true时，这个true只会退出当前层的递归函数实例，返回到上一层的递归调用位置；而上一层接住返回值后没有做任何返回处理，会顺着代码逻辑继续走到函数末尾的return false，再把false往更上层传递，最终最外层拿到的结果永远是false，看起来就像return true语句完全没生效。
• 代码还存在一个边界逻辑bug：现有逻辑仅在数组长度大于1时做值匹配判断，当递归收敛到数组长度为1时，会直接跳过所有判断返回false，如果目标值刚好是最后剩下的这个单元素，会出现漏判。

只需要做两处修改即可：

• 在左右两个分支的递归调用前加上return关键字，把深层递归的返回值直接透传给上一层调用栈
• 补全长为1的数组的匹配判断逻辑，不要直接返回固定值false

修复后的完整代码如下：

// 输入数组必须提前升序排序才可使用二分查找
fun binarySearch(inputArray: Array<Int>, itemToSearch: Int) : Boolean {
    // 打印日志方便观察搜索过程的区间变化
    println()
    inputArray.forEach {
        print("$it,")
    }

    // 处理单元素区间的边界场景
    if (inputArray.size == 1) {
        return inputArray[0] == itemToSearch
    }

    val midIndex = (inputArray.size / 2) - 1
    val midValue = inputArray[midIndex]
    if (itemToSearch == midValue) {
        return true
    }
    // 递归调用前加return，透传子调用的返回结果
    return if (itemToSearch > midValue) {
        binarySearch(inputArray.copyOfRange(midIndex + 1, inputArray.size), itemToSearch)
    } else {
        binarySearch(inputArray.copyOfRange(0, midIndex), itemToSearch)
    }
}

对应给出的测试用例验证：

val result = binarySearch(arrayOf(1,2,3,4,5,6,7,8,9,10,11,12,13,14,16,17,18,19,20,21,22,23), 16)
println(result) // 输出true，符合预期

内容的提问来源于stack exchange，提问作者Martin Bove