# Summary: search in rotated sorted array (with/without duplicates). Java Solution

• "Binary search is the easiest hardest problem."

I spent a while trying to think of an idea that could solve both this problem and also the problem with duplicates, and here are my solutions. Hope it would help:)

1. Let's first talk about the problem without duplicates (which I believe is easier). The key is to find the sorted half part of the array.
``````public class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length-1;
while (left <= right) {
if (left == right)
return nums[left] == target ? left:-1;
int mid = left + (right - left)/2;
if (nums[mid] == target) return mid;
if (nums[mid] <= nums[right]) {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
} else {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}
return -1;
}
}
``````
1. As for the problem with duplicates, we only need to modify a few lines in the solution above. The most significant change is that we need to specifically discuss the case where nums[mid] == nums[right]:
``````public class Solution {
public boolean search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while ( left <= right) {
if (left == right)
return nums[left] == target;
int mid = left + (right-left)/2;
if (nums[mid] == target) {
return true;
}
if (nums[mid] < nums[right]) {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
} else if (nums[mid] > nums[right]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else if (nums[mid] == nums[right]) {
right--;
}
}
return false;
}
}
``````

• Thanks for sharing.

But, regarding the one with duplicates handling,
could you explain, "else if (nums[mid] > nums[right])" a little?
I know it means the left part of the array is sorted,
but why "nums[mid] > nums[left]" doesn't work?

• It's because when mid == left (which would happen occasionally since divide in java is rounding down), the left half is sorted, but it would not satisfy the condition nums[mid] > nums[left]. Then it means we might need to go to the last condition, which leads to right--. (for example, cases like [1,3], given target = 3).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.