"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:)

- 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;
}
}
```

- 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;
}
}
```