java - 二进制搜索计数比较

Question

我有这种方法，我有一个整数数组，我想显示进行了多少比较。 （int键）是我必须搜索一个整数，如果整数不存在于数组中。

public static int binarySearch(int[] inputArray,int key) {
    int start = 0;
    int end = inputArray.length - 1;

    while (start <= end) {

        int mid = (start + end) / 2;

        if (key == inputArray[mid]) {
            return mid;
        }

        if (key < inputArray[mid]) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return -1;
}

Answer 1

在您已设定条件的每个地方都在进行比较。您可以拥有一个实例变量，并在所有此类位置将其增加，例如

int counter = 0;
public static int binarySearch(int[] inputArray,int key) {
    int start = 0;
    int end = inputArray.length - 1;

    while (start <= end) {
        counter++;
        int mid = (start + end) / 2;

        if (key == inputArray[mid]) {
            counter++;
            return mid;
        }

        if (key < inputArray[mid]) {
            counter++;
            end = mid - 1;
        } else {
            counter++;
            start = mid + 1;
        }
    }
    return -1;
}