Search in Rotated Sorted Array II

• leetcode 81
• Medium
• Tags: Array, Binary Search
• Similar Problems: Search in Rotated Sorted Array

  Description

  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.

Previous Thinking

• Compare with the previous version, the difference is duplicates are allowed.
• nums[first] <= nums[mid] could not be used as the condition to claim the ascending in this range.
• We should break the previous condition into two conditions: nums[first] == nums[mid] and nums[first] < nums[mid].
• If nums[first] < nums[mid], we can still claim the ascending trend.
• Otherwise, first++ to see the next step.

C++ Solution

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int first = 0, last = nums.size() - 1;

        while(first <= last){
            int mid = first + ( last - first) / 2;
            if(nums[mid] == target){
                return true;
            }

            if(nums[first] < nums[mid]){
                if(nums[first] <= target && target < nums[mid])
                    last = mid - 1;
                else
                    first = mid + 1;
            }
            else{
                if(nums[first] > nums[mid]){
                   if( nums[mid] < target && target <= nums[last])
                       first = mid + 1;
                   else
                      last = mid - 1;
                }
                else
                    first++;
            }
        }
        return false;
    }
};

Java Solution

public class Solution {
    public boolean search(int[] nums, int target) {
        int first = 0, last = nums.length - 1;
        while(first <= last){
            int mid = (first + last) / 2;
            if(nums[mid] == target) return true;

            if(nums[first] < nums[mid]){
                if(nums[first] <= target && target < nums[mid]){
                    last = mid - 1;
                }else{
                    first = mid + 1;
                }
            }else if(nums[first] > nums[mid]){
                if(nums[mid] < target && target <= nums[last]){
                    first = mid + 1;
                }else{
                    last = mid - 1;
                }
            }else{
                first ++;
            }
        }

        return false;
    }
}

Post Thinking

This is a good question to make us thinking about what duplicate actually means. And how to deal with the duplicates. Usually it affects the condition<= , we should examine this condition carefully and break it into < and ==.