LeetCode每日一题：search in rotated s

问题描述

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.

问题分析

和上一题不同，由于存在相同的数，所以不能直接分成两部分，如{1，2，1，1}，

• 不能使用A[low]<=A[mid]来作为递增有序序列了
• 若A[low]<A[mid],则[low,mid]为递增有序序列
• 若A[low]=A[mid],则low++，知道满足A[low]<A[mid]

讽刺的是这题用上题的代码也可以AC，花费116ms/3191KB；用下面的代码AC是花费112ms/3191KB，几乎一样的。

代码实现

public boolean search(int[] A, int target) {
        int low = 0;
        int high = A.length - 1;
        int mid = 0;
        while (low <= high) {
            mid = (low + high) / 2;
            if (A[mid] == target) return true;
            else if (A[mid] > A[low]) {
                if (A[low] <= target && target <= A[mid]) high = mid - 1;
                else low = mid + 1;
            } else if (A[mid] < A[low]) {
                if (A[high] >= target && target >= A[mid]) low = mid + 1;
                else high = mid - 1;
            } else low++;
        }
        return false;
    }