Leetcode and Lintcode

Search in Rotated Sorted Array II

Problem:

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.

Leetcode link
Lintcode link

My Solution:

Compared to the “Search in Rotated Sorted Array”, the elements can be duplicate, so we can not know the start point is on the left part or right part, even if we have “nums[left] <= nums[mid]”.

We can only judge when “nums[left] < nums[mid]”. So if “nums[left] == nums[mid]”, we can add left lie “left++” until “nums[left]” and “nums[right]” are different. Code implemented in ‘search’ method.

The time complexity is O(n).

Solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/*************************************************************************
	> File Name: SearchInRotatedArrayII.java
	> Author: Yao Zhang 
	> Mail: psyyz10@163.com 
	> Created Time: Tue 10 Nov 18:16:29 2015
 ************************************************************************/

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

Solution 1 is better to return an index. If we just need to return boolean, a brute force method is ok, like Solution 2.

1
2
3
4
5
6
public boolean search2(int[] nums, int target) {
   	for (int n : nums){
   		if (n == target) return true;
   	}
   	return false;
   }

Related Problem:
Search in Rotated Sorted Array