Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., `[1, 4, 6, 8, 11, 13, 15]` might become `[8, 11, 13, 15, 1, 4, 6]`).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array. Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

``````Input: nums = [8, 11, 13, 15, 1, 4, 6], target = 1
Output: 4
``````

Example 2:

``````Input: nums = [1, 4, 6, 8, 11, 13, 15], target = 3
Output: -1
``````

## Rotated Sorted array search solution in Java

We can apply binary search to find the element in the array in `O(log(n))` time complexity. Following is the solution to the problem with comments for clarity:

``````class RotatedSortedArraySearch {
private static int search(int[] nums, int target) {
int left = 0;
int right = nums.length-1;

while(left <= right) {
int mid = (left+right)/2;
if(target == nums[mid]) {
return mid;
}

if(nums[left] <= nums[mid]) { // left part is sorted
if(target >= nums[left] && target < nums[mid]) {
// target lies between left and mid index
right = mid-1;
} else {
left = mid+1;
}
} else { // right part is sorted
if(target > nums[mid] && target <= nums[right]) {
// target lies between mid and right index
left = mid+1;
} else {
right = mid-1;
}
}
}

return -1;
}

public static void main(String[] args) {
int[] nums = {8, 11, 13, 15, 1, 4, 6};
int target = 1;

System.out.println(search(nums, target));
}
}
``````
``````# Output
\$ javac RotatedSortedArraySearch.java
\$ java RotatedSortedArraySearch
4
``````