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

Question

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

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，则语句不会递增。我也不能将它们放在选择语句之间，因为那样会给我 else 而不会出现 if 错误。我想知道使用递归进行搜索是否是个坏主意，但我想相信这是可能的。任何帮助将不胜感激。

Answer 1

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

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;
}

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

Incrementing statements to track comparisons in recursive method

java

arrays

recursion

increment

binary-search