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.

实现代码：

public class Solution { 
    public static boolean search(int[] nums, int target) { 
		int index=0; 
	    for(int i=0;i<nums.length-1;i++){ 
	    	if(nums[i] > nums[i+1]){ 
	    		index = i+1; 
	    		break; 
	    	} 
	    } 
	    int left=0,right=nums.length-1; 
	    if(target > nums[right]){ 
	    	right=index-1; 
	    }else if(target < nums[right]){ 
	    	left=index; 
	    }else if(index!=0 && target==nums[right]){ 
	    	return true; 
	    } 
	    index=(left+right)/2; 
	    while(left <= right){ 
	    	System.out.println("000000"); 
	    	if(target < nums[index]){ 
	    		right=index-1; 
	    	}else if(target > nums[index]){ 
	    		left=index+1; 
	    	}else{ 
	    		return true; 
	    	} 
	    	index=(left+right)/2; 
	    	 
	    } 
		return false; 
    } 
}