二分查找_二分查找 java_二分查找最多比较次数

在《二分查找法的实现和应用汇总》中，我介绍了二分查找法的基本应用，不过在面试的准备过程中，我还碰到了更多对于二分查找法的更进一步的使用。其实在《二分查找法的实现和应用汇总》的最后，我已经介绍了一个非常规的使用，也就是基于“轮转后的有序数组（Rotated Sorted Array）”检查某一个数是否存在。

对于普通的有序数组来说，这个问题是非常简单的，因为数组中的第K-1个数（即A[K-1]）就是所要找的数，时间复杂度是O(1)常量。但是对于轮转后的有序数组，在不知道轮转的偏移位置，我们就没有办法快速定位第K个数了。

不过我们还是可以通过二分查找法，在log(n)的时间内找到最小数的在数组中的位置，然后通过偏移来快速定位任意第K个数。当然此处还是假设数组中没有相同的数，原排列顺序是递增排列。

在轮转后的有序数组中查找最小数的算法如下：

//return the index of the min value in the Rotated Sorted Array, whose range is [low, high]
int findIndexOfMinVaule(int A[], int low, int high)
{
    if (low > high) return -1;
    while (low < high) {
        int mid = (low + high)/2;
        if (A[mid] > A[high])
            low = mid +1;
        else
            high = mid;
    }
    
    //at this point, low is equal to high
    return low;
}

接着基于此结果进行偏移，再基于数组长度对偏移后的值取模，就可以找到第K个数在数组中的位置了：

int findKthElement(int A[], int m, int k)
{
    if (k > m) return -1;
    int base = findIndexOfMinVaule(A, 0, m-1);
    int index = (base+k-1)%m;
    return index;
}

之前我谈到，对于一个有序数组来说，找到第K个数是非常简单的，假如我们有两个有序的数组，希望从中找到第K小的数呢？

这个问题最直观的解决方法就是像归并排序中的归并算法那样，从头开始比较，找到那第K小的数，那么平均时间复杂度就是O(m+n)，其中m，n分别是两个数组的长度。

不过通过二分查找法，得到一个复杂度为O(log(m+n))的算法（很多地方说这个算法的复杂度是O(log m + log n)，我没有进行准确的演算和统计，但是个人认为O(log(m+n))才对）。先来看算法代码，然后来分析（或者你也可以看这篇文章）。

这里对于参数的假设如下：数组的索引是以0为基数并且m+n > 0；k是以1为基数并且1<=k <= m+n，两个数组的集合没有重复元素。在这样的假设下，暗示我们总是可以找到那个第k个数。

//return the value of kth element in union of two sorted array
int findKthElement(int A[], int m, int B[], int n, int k) {
    int i = int(double(m)/(m+n)*(k -1));
    int j = (k-1) - i;
    
    //A[i] or B[j] is the Kth element, return it
    if ((j <= 0 || B[j-1] < A[i]) && (j >= n || A[i] < B[j]))
        return A[i];
    if ((i <= 0 || A[i-1] < B[j]) && (i >= m || B[j] < A[i]))
        return B[j];
    
    //A[i] is too small, get rid of lower part of A and higher part of B
    if (0 < j && A[i] < B[j-1])
        return findKthElement(A+i+1, m-i-1, B, j, k-i-1);
    
    //B[j] is too small, get rid of higher part of A and lower part of B
    else //if(i > 0 && B[j] < A[i-1]) 
        return findKthElement(A, i, B+j+1, n-j-1, k-j-1);
}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-30980-1.html