# Java Solution with Super Detailed Explanation

• We all know how to do binary search. The only thing we need to find out is when we need to go the opposite way (compared to normal binary search). Suppose we have a center part of a rotated array:
`... a b c x d e f g ...`
Let `a` be `arr[lo]` and `g` be `arr[hi]`. Binary search will find `x` as `arr[mid]`. Now we need to decide to search left or search right.

Some basic knowledge:
When dealing with rotated array, we search differently than normal binary search. We know `x = arr[mid]`, and `target > x` or `target < x`, but in either case, `target` can still be on the left or right of `x`. We need more information to confirm where our `target` is.

First thing is how to check if array is rotated: `arr[lo] > arr[hi]`. Done.

Next, we want to check if x is on the left or right part of the rotated array. For example, given array `[4, 5, 1, 2, 3]`, we define `[4, 5]` as the left part and `[1, 2, 3]` as the right part. Though the array is rotated, the left and right parts will remain sorted, so anything in the left part should be `>= arr[lo]`, and anything in the right part should be `< arr[lo]`. But since `arr[lo] > arr[hi]` in a rotated array (without duplicates), for the left part, `>= arr[lo]` can be replaced by `> arr[hi]`, and for the right part, `< arr[lo]` can be replaced by `<= arr[hi]`. Thus, if `x >= arr[lo] or x > arr[hi]` then `x` is in the left part, and if `x < arr[lo] or x <= arr[hi]` then x is in the right part.

Finally, we want to check where our `target` belongs to. We have already proven that `x >= arr[lo] or x > arr[hi]` when x is in the left part, and `x < arr[lo] or x <= arr[hi]` when x is in the right part, and if we use it, we can see that `target` is in the left part when `target >= arr[lo] or target > arr[hi]`, and `target` is in the right part if `target < arr[lo] or target <= arr[hi]`.

There are 3 cases:

1. `x > target`.
Now let's consider all possible cases:
For rotated array:
a) `x` and `target` both in left or right part. But since `x > target`, and left and right parts are both sorted, we have to go left to search for `target`.
b) `x` is in left part and `target` is in right part. This is possible because `x > target`, and we know `numbers in the left part > numbers in the right part`. Thus to find `target`, we need to search to the right in this case.
c) `x` is in right part and `target` is in left part. This is impossible since in rotated array, `arr[lo] > arr[hi]`, and we already have `x > target`. This condition can be written as: `array is rotated, x is in the left part, and target is in the right part`, or equivalently `nums[lo] > nums[hi] && target <= nums[hi] && nums[mid] >= nums[lo]`.
For unrotated array:
d) The array is not rotated, if we have `x > target` we simply search left for `target`.

We found for case a and d, we search to the left. Only in case b do we search to the right. It boils down to:

``````if (nums[mid] > target) {
if (nums[lo] > nums[hi] && target <= nums[hi] && nums[mid] >= nums[lo]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
``````
1. `x < target`. In normal binary search we would need to search right. In rotated array we don't. The idea is the same as above. We want to find the "outlier" case when we search to the left. Cases can be:
For rotated array:
a) `x` and `target` both in left or right part. But since `x < target`, target can only be on right side of x.
b) `x` in left and `target` in right. We have already proven that `arr[lo] > arr[hi]`, and every element in left part should be greater than right part, so this is not possible.
c) `x` in right and `target` in left, this is the only case where we need to search to the left because `target` is on the left side of `x`. The condition for this can be written as: `array is rotated, and x is on the right part, and target is on the left part`, which is equivalent to: `nums[lo] > nums[hi] && target >= nums[lo] && nums[mid] <= nums[hi]`.
For unrotated array:
d) `x < target` implies `x` is on the left side of `target`, so we must go left.

Thus it boils down to:

``````else if (nums[mid] < target) {
if (nums[lo] > nums[hi] && target >= nums[lo] && nums[mid] <= nums[hi]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
``````
1. `x == target`. We have found the target value. This is trivial.
``````public class Solution {
public int search(int[] nums, int target) {
if (nums == null) return -1;
int lo = 0, hi = nums.length-1;
while (lo <= hi) {
int mid = (hi-lo)/2 + lo;
if (nums[mid] > target) {
if (nums[lo] > nums[hi] && target <= nums[hi] && nums[mid] >= nums[lo]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
} else if (nums[mid] < target) {
if (nums[lo] > nums[hi] && target >= nums[lo] && nums[mid] <= nums[hi]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
} else {
return mid;
}
}
return -1;
}
}
``````

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