algorithm - 在 k 排序的数组中查找 k

Question

我正在尝试编写一个类似于二进制搜索的算法来在 k 排序的数组中找到 k。 (需要为 O(logn))

比如这里的k是3:5、6、7、1、2、3、4

这是我在 Java 中的尝试

public static int findk(int[] a) {
    int low = 0;
    int high = a.length-1;

    while(low <= high) {
        if(a[low] <= a[high])
            return low;

        int middle = (low+high)/2;
        if(a[low] > a[middle])
            high = middle-1;
        else
            low = middle+1;
    }

    return 0;
}

它适用于某些输入，但不适用于其他输入。这应该很容易，但我不知道出了什么问题。

即使是提示也会很好!

Answer 1

您需要找到第一个小于 a[0] 的元素。因此，您需要与 a[0] 进行比较。

public static int findk(int[] a) {
    int low = 0;
    int high = a.length - 1;
    if (a[high] >= a[0]) // special case array completely sorted
        return high + 1;
    while(low < high) {
        int middle = (low + high) / 2;
        if(a[middle] < a[0])
            high = middle;
        else
            low = middle + 1;
    }    
    return low; // or high
}

开始时你会得到 [0,6]，然后是 [0,3]，然后是 [2,3]，最后是 [3,3]。

我们不做 high = middle - 1 的原因是这样我们可能会得到我们不想要的 k 值。