# Search an element in a Rotated Sorted Array

## Rotated Sorted array search

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

Although the entire array is not sorted from left to right, the subarray on the left of the pivot and on the right of the pivot will still be sorted. We can use this fact and 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
```