如何实现针对字符串的递归二分查找？已有迭代版本转递归遇阻

递归版二分查找的核心逻辑和迭代版一致，只是把循环替换成递归调用，每次根据字符串比较结果缩小查找范围，直到找到目标或确定目标不存在。

递归版代码实现 #

static void binarySearchRecursive(String[] words, String word, int left, int right) {
    // 终止条件：查找范围失效，说明目标不存在
    if (left > right) {
        return;
    }

    int middle = left + (right - left) / 2;
    int result = word.compareTo(words[middle]);

    // 找到目标字符串，输出并返回
    if (result == 0) {
        System.out.println(words[middle]);
        return;
    }

    // 目标比中间元素大，递归查找右半部分
    if (result > 0) {
        binarySearchRecursive(words, word, middle + 1, right);
    } 
    // 目标比中间元素小，递归查找左半部分
    else {
        binarySearchRecursive(words, word, left, middle - 1);
    }
}

和迭代版的对比说明 #

你的迭代版代码通过while循环持续缩小范围，而递归版则是：

• 用left > right作为递归终止条件（对应迭代版中循环结束的条件）
• 每次递归调用时直接传入新的left或right边界（对应迭代版中更新left/right的操作）
• 同样依赖String.compareTo()方法来比较字符串大小，这是字符串二分查找的关键（前提是数组已按字典序排序）

注意事项 #

• 必须保证输入的words数组是按字典序升序排序的，否则二分查找无法正确工作
• 递归深度过大会导致栈溢出，不过对于常规长度的字符串数组，这个问题可以忽略

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