LeetCode:Search in Rotated Sorted Array I II

LeetCode:Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array. 本文地址

分析：顺序查找肯定是可以的，可不可以找出效率更高的查找算法？其实二分查找也可以用在这里。那么和普通的二分查找有什么区别呢？

当target < A[middle]时，普通二分查找是让查找区间右边界iend = middle - 1，这一题中不能直接这么操作，因为我们查找的元素有可能在middle的后半段，例如在5 6 7 8 9 1 2 3中查找2，中间元素时8, 虽然2 < 8, 但是我们还是要在middle后半段查找，那么什么时候会出现这种情况呢，要满足三个条件：

a、查找区间的尾部元素小于首部元素，这表示查找区间不是全部有序的，

b、target不大于查找区间的尾部元素，这表示target在旋转前数组的前半部分，

c、中间元素要大于查找区间尾部元素，这表示中间元素在旋转前数组的后半部分。

如果没有同时满足这三个条件那么我们要去middle的前半段查找。

当target > A[middle]时，普通二分查找要到middle后半段查找，这一题中比如在7 8 9 1 2 3 5 6中查找8, 中间元素时1，8 > 1但是还是需要到前半段查找。到前半段查找时，也需要同时满足三个条件：

a、查找区间的尾部元素小于首部元素，这表示查找区间不是全部有序的

b、target大于查找区间的尾部元素，这表示target在旋转前数组的后半部分

c、中间元素要小于查找区间尾部元素，这表示中间元素在旋转前数组的前半部分。

如果没有同时满足这三个条件那么我们要去middle的后半段查找。

当target = A[middle]时直接返回查找结果

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

LeetCode:Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

分析：上一题的所有分析是基于数组中没有重复元素的，如果存在重复元素，情况会如何呢？

修正条件a：对于上一题的三个条件中的a条件，当查找区间尾部元素等于首部元素时，也有可能表示查找区间不是有序的，比如1 1 1 3 1
修正条件c：当中间元素等于尾部元素时，也可能满足上面的条件，比如target = 3，数组为1 1 1 3 1，或者target = 1，数组为3 3 3 1 3
当三个条件都满足时，如果中间元素等于尾部元素，我们不能确定是向哪个方向继续查找，例如target = 3，查找区间为1 1 1 3 1和1 3 1 1 1都满足target > 中间元素时的三个条件，但是两个区间分别是向middle的不同方向查找，因此此时查找区间不能折半，只能让区间的右边界减1

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

在leetcode的discuss里看到了另一种思路的解法，通过判断查找区间首部元素和中间元素的关系来判断查找区间的哪一部分是有序的

没有重复元素的情形下：

如果中间元素大于首部元素，那么表明查找区间左半部分是有序的，然后再根据target是否在有序的一部分来决定接下来查找的方向
如果中间元素小于首部元素，那么查找区间有半部分是有序的，然后再根据target是否在有序的一部分来决定接下来查找的方向
如果中间元素等于首部元素，此时只有可能是查找区间包含一个或两个元素的情形，让左边界加1继续查找即可（相当于左边界 = middle + 1，因为此时midlle等于左边界）

包含重复元素的情形：

前两种情况一样，最后一种情况当中间元素等于首部元素时，查找区间有可能不再只包含一个或两个元素，此时没法判断哪一部分有序，只能将查找区间左边界加1，其实操作和上面是相同的

两题都可以用以下代码(稍微修改返回值)

class Solution {
public:
    bool search(int A[], int n, int key) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int m = l + (r - l)/2;
        if (A[m] == key) return true; //return m in Search in Rotated Array I
        if (A[l] < A[m]) { //left half is sorted
            if (A[l] <= key && key < A[m])
                r = m - 1;
            else
                l = m + 1;
        } else if (A[l] > A[m]) { //right half is sorted
            if (A[m] < key && key <= A[r])
                l = m + 1;
            else
                r = m - 1;
        } else l++;
    }
    return false;
    }
};

参考资料：http://oj.leetcode.com/discuss/223/when-there-are-duplicates-the-worst-case-is-could-we-do-better