java - 递增语句以跟踪递归方法中的比较

Question

我正在尝试构建一种递归二分搜索方法，该方法在可比较对象的排序数组中搜索感兴趣的对象。这是一个更大算法的一部分，该算法搜索已排序数组的集合并查找集合中所有数组共有的元素。目标是使算法的搜索/比较部分尽可能高效。线性解应该是可能的。方法是这样的:

private static boolean BinarySearch(Comparable[] ToSearch, Comparable ToFind, int first, int last){
    boolean found = false;
    int mid = first + (last - first) / 2;
    comparisons++;
    if(first > last){
        found = false;
    }
    else if(ToFind.compareTo(ToSearch[mid]) == 0){
        found = true;
        comparisons++;
    }
    else if(ToFind.compareTo(ToSearch[mid]) < 0) {
        found = BinarySearch(ToSearch, ToFind, first, mid - 1);
        comparisons++;
    }
    else{
        found = BinarySearch(ToSearch, ToFind,mid + 1, last);
        comparisons++;
    }
    return found;
}

我遇到的问题是通过递归跟踪比较的次数。因为我必须计算计算结果为 false 和 true 的比较，所以我尝试将比较递增语句放置在每个选择语句中，但这不起作用，因为如果语句计算结果为 false，则该语句不会递增。我也不能将它们放在选择语句之间，因为这会给我带来没有 if 错误的 else 。我想知道使用递归进行搜索是否是一个坏主意，但我想相信这是可能的。任何帮助将不胜感激。

Answer 1

也许您可以在每个 if block 中设置一个变量，其中包含到达该位置所需的比较次数，并将其添加到末尾？

private static boolean BinarySearch(Comparable[] ToSearch, Comparable ToFind, int first, int last){
    boolean found = false;
    int newComparisons = 0;
    int mid = first + (last - first) / 2;
    if(first > last){
        found = false;
        newComparisons = 1;
    }
    else if(ToFind.compareTo(ToSearch[mid]) == 0){
        found = true;
        newComparisons = 2;
    }
    else if(ToFind.compareTo(ToSearch[mid]) < 0) {
        found = BinarySearch(ToSearch, ToFind, first, mid - 1);
        newComparisons = 3;
    }
    else{
        found = BinarySearch(ToSearch, ToFind,mid + 1, last);
        newComparisons = 3;
    }
    comparisons += newComparisons;
    return found;
}