Search in Rotated sorted array with duplicates
https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
Solution I: iterative
public boolean search(int[] nums, int target) {
int left=0;
int right=nums.length-1;
while(left<=right){
int mid = (left+right)/2;
if(nums[mid]==target)
return true;
if(nums[left]<nums[mid]){
if(nums[left]<=target&& target<nums[mid]){
right=mid-1;
}else{
left=mid+1;
}
}else if(nums[left]>nums[mid]){
if(nums[mid]<target&&target<=nums[right]){
left=mid+1;
}else{
right=mid-1;
}
}else{
left++;
}
}
return false;
}
Solution II: recursive
public class Solution {
public boolean search(int[] nums, int target) {
if (nums.length == 0) {
return false;
}
return search(nums, 0, nums.length-1, target);
}
public boolean search(int[] nums, int left, int right, int target) {
if (left > right) {
return false;
}
int mid = left + (right-left)/2;
if (nums[mid] == target) {
return true;
}
if (nums[left] < nums[mid]) {
if (target >= nums[left] && target < nums[mid]) {
return search(nums, left, mid-1, target);
}
return search(nums, mid+1, right, target);
}
else if (nums[left] > nums[mid]) {
if (target > nums[mid] && target <= nums[right]) {
return search(nums, mid+1, right, target);
}
return search(nums, left, mid-1, target);
}
else {
return search(nums, left+1, right, target);
}
}
}