查找比较次数

Question

我正在尝试跟踪此二进制搜索代码中的键比较次数。对于 2^16 的数组大小，比较结果应该在 17 左右。你能解释一下为什么我会得到 33 吗？

public class AdvancedBinarySearch {

    int count = 0;

    // Returns location of key, or -1 if not found 
    int AdvancedBinarySearch(int arr[], int l, int r, int x) {
        int m;

        while (r - l > 1) {
            count++;
            m = l + (r - l) / 2;
            if (arr[m] <= x) {
                l = m;
                count++;
            } else {
                r = m;
                count++;
            }
        }

        if (arr[l] == x) {
            count++;
            return l;
        }

        if (arr[r] == x) {
            count++;
            return r;

        } else {
            count++;
            return -1;

        }
    }

    public void setCount(int i) {
        this.count = i;
    }
}

Answer 1

您的代码对 if (arr[m] <= x) 比较进行了两次计数。如果您从 l = m 下方以及 r = m 下方移除 count++，则不会再发生这种情况。

我在这个变化前后测试了这个，在一个从 0 到 65535 的整数数组中搜索 189。这个数组的大小是 2^16，在变化之前，计算了 33 次比较，之后这个变化，计算了 17 次比较，所以我认为这个变化做了你想要它做的。