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

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

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 = [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

Output

4

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

Leave a Reply

Your email address will not be published. Required fields are marked *