在k排序数组中查找k

您需要找到第一个小于[0]的元素。因此,您需要与[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值。