# O(logn) Java solution with Derivation

• First of all, we would divide the problem into two cases:

Case 1: Sorted array is not rotated
Then it becomes a simple binary search problem and I assume you know the solution to it : )

Case 2: Sorted array is rotated
Assume that the rotated sorted array looks like this
l1...r1l2...r2 where l2 <= r2 < l1 <= r1

And we shall start list down all the possible combinations involving m (median) and target and the corresponding action

target > m
l1<=m...target...r1l2...r2 -> l1=m+1
l1...r1l2...m...target<=r2 -> l1=m+1
l1<=target...r1l2...m<=r2 -> r2=m-1

target < m
l1<=target...m...r1l2...r2 -> r2=m-1
l1<=m...r1l2...target<=r2 -> l1=m+1
l1...r1l2...target...m<=r2 -> r2=m-1

And here is my solution based on my previous analysis:

``````class Solution {
public int search(int[] nums, int target) {
int l = 0;
int r = nums.length-1;

while (l <= r) {
int m = l + (r-l) / 2;

if (nums[l] < nums[r]) {
if (nums[m] > target) {
r = m-1;
} else if (nums[m] < target) {
l = m+1;
} else {
return m;
}
} else {
if (nums[m] > target) {
if (nums[l] <= nums[m] && target <= nums[r]) {
l = m+1;
} else {
r = m-1;
}
} else if (nums[m] < target) {
if (nums[l] <= target && nums[m] <= nums[r]) {
r = m-1;
} else {
l = m+1;
}
} else {
return m;
}
}

}

return -1;
}
}
``````

Combine some condition check to make code more cleaner and unreadable:

``````class Solution {
public int search(int[] nums, int target) {
int l = 0;
int r = nums.length-1;

while (l <= r) {
int m = l + (r-l) / 2;
if (nums[m] > target) {
if (nums[l] <= nums[m] && target <= nums[r] && nums[l] >= nums[r]) {
l = m+1;
} else {
r = m-1;
}
} else if (nums[m] < target) {
if (nums[l] <= target && nums[m] <= nums[r] && nums[l] >= nums[r]) {
r = m-1;
} else {
l = m+1;
}
} else {
return m;
}
}

return -1;
}
}
``````

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