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