将使用Comparator的迭代版首次出现位置二分查找改写为递归实现的问题

改写可行性确认 #

迭代实现的首元素匹配二分查找完全可以改写为递归版本，二分查找的核心逻辑是不断缩小搜索区间，天然适配递归分治的思想，改写后逻辑一致性不会受影响。

实现思路 #

• 外层入口方法保留原有参数校验逻辑，校验通过后调用私有递归辅助方法，辅助方法额外传入当前搜索区间的上下界low和high
• 递归终止条件：
  • 当low > high时说明未匹配到目标，返回-1
  • 当匹配到目标且确认是首次出现时，直接返回当前下标
• 区间收缩逻辑和迭代版保持一致：
  1. 目标key小于中间元素：递归搜索左半区间[low, mid - 1]
  2. 目标key大于中间元素：递归搜索右半区间[mid + 1, high]
  3. 目标key等于中间元素：判断当前元素的前一位是否和它相等（且下标合法），如果相等说明还有更早的匹配项，继续递归搜索左半区间，否则当前下标就是首次出现的位置

递归版完整代码 #

public static <Key> int firstIndexOf(Key[] a, Key key, Comparator<Key> comparator) {
    // 原有参数校验逻辑保持不变
    if (a == null || key == null || comparator == null) {
        throw new NullPointerException("Arguments cannot be null.");
    }
    // 可选优化：提前判断首元素匹配的情况，减少递归次数
    if (comparator.compare(a[0], key) == 0) {
        return 0;
    }
    // 调用递归辅助方法，初始区间是整个数组
    return firstIndexOfRecursive(a, key, comparator, 0, a.length - 1);
}

private static <Key> int firstIndexOfRecursive(Key[] a, Key key, Comparator<Key> comparator, int low, int high) {
    // 递归终止条件：区间无效，未找到
    if (low > high) {
        return -1;
    }
    int mid = low + (high - low) / 2;
    int cmp = comparator.compare(key, a[mid]);
    if (cmp < 0) {
        // 目标更小，搜索左半区
        return firstIndexOfRecursive(a, key, comparator, low, mid - 1);
    } else if (cmp > 0) {
        // 目标更大，搜索右半区
        return firstIndexOfRecursive(a, key, comparator, mid + 1, high);
    } else {
        // 匹配到目标，判断是否是第一个出现的
        if (mid > 0 && comparator.compare(a[mid - 1], a[mid]) == 0) {
            // 前面还有相同元素，继续往左找
            return firstIndexOfRecursive(a, key, comparator, low, mid - 1);
        } else {
            // 已经是第一个出现的
            return mid;
        }
    }
}

补充说明 #

递归版本和迭代版本的时间复杂度一致，均为O(log n)，仅空间复杂度有差异：递归版因为需要存储递归栈帧，空间复杂度为O(log n)，迭代版为O(1)。但由于二分查找的递归深度极低（长度为100万的数组递归深度仅为20左右），实际使用中不会出现栈溢出问题，性能差异可以忽略。

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