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:

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

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

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