LeetCode: Search in Rotated Sorted Array I && II

I

似乎也是一个存在复杂技巧的问题，不过这里就不进行过度优化了，直接两次二分查找即可，反正复杂度是一样的因为每次二分查找只查找了序列的一部分，并且实现起来简洁漂亮。简而言之，没必要做过度优化。

2015.1.3更正：上述做法显然是错误的，如果想要拆分成两次二分查找，意味着需要遍历数组找出转折点——这个复杂度已经是O(n)了！正确的做法是利用类似二分查找的性质。考虑到题目保证元素不重复，因此这是个单调递增的序列被“旋转”，则当求mid之后，有且只有以下两种情况：

示意图

如果A[mid]>A[low]，则属于落在区间1中的情况；否则，则属于落在区间2中的情况。我们仅分析前者的情形，因为对于后者而言是对称的。在区间1中，A[mid]将区间分为左右两部分，考察target与A[mid]的相对大小关系：如果target<A[mid]，则target可能位于区间1的左侧，或者整个区间2中，这两种情况均满足条件，所以不能只用这样一个简单的判断条件来二分区间。

因此，我们增加一个判断条件：如果target<A[mid]&&target>=A[low]，才能够保证target一定位于区间1的左侧；如果不满足的话，它就应该位于区间1的右侧与整个区间2所连起来的部分。这样，我们就完成了有效的二分操作，成功地将问题规模减半，算法复杂度达到O(log(n))。

II

~~题目允许重复元素，但是转换成裸的二分查找也明明可以的啊亲！！！何必要分析那么复杂的情况呢？~~

2015.1.3更新：这题与对应的上一题仅仅存在着微妙的不同。由于允许存在重复的元素，因此我们无法仅仅通过比较A[low]与A[mid]的相对大小，来区分A[mid]元素属于两种情况中的哪一种，因为如果序列前面有大量重复元素的话，会导致A[low]==A[mid]。因此，在这种情况下，我们只能将左侧low指针右移一个位置，以期望它走出这片元素重复的区域，从而使得程序能够区分出A[mid]所处的位置。这样，在极端情况下，例如数组中元素完全相同的话，将导致算法的最坏复杂度退化至O(n)，但是平均情形下还是会非常快的。

代码

第一问

class Solution {
public:
    int search(int A[], int n, int target) {
        int l = 0, r = n;
        while ( l < r ) {
            int mid = ( l + r ) / 2;
            if ( A[mid] == target ) return mid;
            if ( A[mid] >= A[l] ) {
                if ( target < A[mid] && target >= A[l] ) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            } else {
                if ( target > A[mid] && target <= A[r - 1] ) {
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
        }
        return -1;
    }
};

第二问

class Solution {
public:
    bool search(int A[], int n, int target) {
        int l = 0, r = n;
        while ( l < r ) {
            int mid = ( l + r ) / 2;
            if ( A[mid] == target ) return true;
            if ( A[mid] > A[l] ) {
                if ( target < A[mid] && target >= A[l] ) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            } else if ( A[mid] < A[l] ) {
                if ( target > A[mid] && target <= A[r - 1] ) {
                    l = mid + 1;
                } else {
                    r = mid;
                }
            } else {
                l++;
            }
        }
        return false;
    }
};