[leetcode]Search in Rotated Sorted Array II

这道题目仍然是二分，去掉不可能的部分。用了递归，在重复的情况下，就是有可能最左边的和最右边的相等，此时就不能直接判断出区间外的元素，左右两边同时递归。有重复元素的时候，在bad case的时候会退化为O（n）

public class Solution {
    public boolean search(int[] A, int target) {
        return search(A, target, 0, A.length-1);
    }
    
    private boolean search(int[] A, int target, int left, int right)
    {
        if( left > right) return false;
        if (left == right) return (A[left] == target);
        if (A[left] < A[right] && (target < A[left] || target > A[right])) return false;
        if (A[left] > A[right] && target > A[right] && target < A[left]) return false;
        int mid = left + (right - left) / 2;
        if (A[mid] == target) return true;
        else
        {
            return search(A, target, left, mid-1) || search(A, target, mid+1, right);
        }
    }
}

网上有个思路更简洁，二分。如果相等导致不能二分，则直接跳过这个重复的元素。

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;
    }
};

[leetcode]Search in Rotated Sorted Array II

相关推荐