import java.util.Arrays;
class Solution {
public boolean search(int[] nums, int target) {
return search(nums, target, 0, nums.length-1);
}
private boolean search(int[] nums, int target, int l, int r){
if( l <= r){
// here we start as a regular binary search
int mid = (r-l)/2 + l;
//if target equals to mid/left/right, return true
// to avoid collision (e.g. difference of target < nums and target <= nums)
// we do it for l, mid, and r
if(target == nums[mid] || target == nums[l] || target == nums[r]){
return true;
}
//here is if there is a rotation in this array/subarray, we call it "twisted"
if(nums[r]>nums[l]){ // if nums[r] > nums[l], nums[l:r] is not a twisted array
if(nums[l] <= target && target <= nums[r]){ // if target in this array, do normal binary search
if(target == nums[mid]){
return true;
}else if(target < nums[mid]){
return search(nums, target, l, mid-1);
}else{
return search(nums, target, mid+1, r);
}
}
//here are cases for twisted array
}else if(nums[mid] == nums[l]){ // if mid and l are the same, we cannot know whether the left is twisted or the right is twisted
// For example, [1,1,1,2,1] has a twisted array at right and [1,2,1,1,1] has a twisted array at left
// But they all satisfy nums[mid] == nums[l]
// Here we can only do O(n) search.
return search(nums, target, l, mid-1)||search(nums, target, mid+1, r);
}
else if(nums[mid] > nums[l]){//if nums[mid] > nums[l], at least left subarray is not twisted array
if(nums[l]<target && target<nums[mid]){ // if target is at left
return search(nums, target, l,mid-1);
}else{ //else
return search(nums, target, mid+1,r);
}
}else{//if nums[mid] > nums[l], at least right subarray is not twisted array
if(nums[mid] < target && target < nums[r]){//if target is at right
return search(nums, target, mid+1, r);
}else{//else
return search(nums, target, l, mid-1);
}
}
}
return false;
}
public static void main(String[] args) {
int[] nums = {1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1};
System.out.println(new Solution().search(nums, 2));
}
}
For further actions, you may consider blocking this person and/or reporting abuse
Top comments (0)