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.

原问题链接：https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

 

问题分析

　　这个问题在之前的一篇文章里有过讨论。对于循环位移之后的排序数组来说，它相当于形成了两段递增的数组。我们还是可以用二分查找的方法去查找元素的。只是查找的过程稍微有点不一样。我们每次去中间值mid的时候，它可能落在前面的一个递增段上，也可能落在后面的一个递增段上。如果落在前面的话，则满足nums[l] < nums[mid]，这个时候需要判断target和nums[mid]的关系，如果它在nums[l]和nums[mid]之间，则将搜索范围缩小到l, mid这里。所以需要将r = mid - 1。否则如果不是这种情况的话，则它肯定在mid + 1, r这个范围。那么就设置 l = mid + 1。

　　如果mid落在后面那个递增段呢，也类似，判断nums[l] > nums[mid]。这个时候就看target是否在mid + 1和r之间，是的话l = mid + 1，否则 r = mid - 1。

　　还有一种情况就是因为问题里提到的有相同的元素，这个时候我们就需要将l向mid的方向移动一位，来逐步逼近缩小搜索范围。

　　详细的代码实现如下：

 

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

　　这个问题的时间复杂度也就是标准二分搜索的时间复杂度，为O(logN)。