Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,

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

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 = [4,5,6,7,0,1,2], target = 0

**Output:**4

**Example 2:**

**Input:**nums = [4,5,6,7,0,1,2], target = 3

**Output:**-1

#### Solution

We can apply binary search to find if target element is present or not. We need to twist the binary search logic as array is rotated.

Due to element rotated in the Array we always have two sorted sub arrays in given input array.

For Example : given array [4,5,6,7,0,1,2] has [4,5,6,7] and [0,1,2] as sub sorted arrays.

We can take advantage of it and first find out in which sub array our target element lies, Once we found that just apply binary search to that sub array only.

###### Code

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
public class SearchInRotatedArray { public static void main(String[] args) { int [] a= {4,5,6,7,0,1,2}; System.out.println(new SearchInRotatedArray().search(a, 0)); } public int search(int[] nums, int target) { if (nums.length == 0) return -1; int pivot = 0; for (int i = 0; i < nums.length; ++i) if (i > 0 && nums[i] < nums[i - 1]) { //Find start point of second sorted array pivot = i; break; } int left = 0, right = nums.length - 1; if (target >= nums[pivot] && target <= nums[right]) //Is element present on first sorted array left = pivot; else right = pivot - 1; //Element present in second sorted array. while (left <= right) { int mid = (left + right) / 2; if (nums[mid] == target) return mid; if (nums[mid] > target) right = mid - 1; else left = mid + 1; } return -1; } } |

#### Output

We encourage you to write a comment if you have a better solution or having any doubt on the above topic.