Binary Search

Search an element in a Rotated Sorted Array

Rajeev SinghAlgorithms1 mins read

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:

import java.util.Scanner;

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

        while(start <= end) {
            int mid = (start + end)/2;

            if(target == nums[mid]) {
                return mid;
            }

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

        return -1;
    }


    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) {
          nums[i] = keyboard.nextInt(); 
        }
        int target = keyboard.nextInt();
        keyboard.close();

        System.out.printf("Search(%d) = %d%n", target, search(nums, target));
    }
}
# Output
$ javac RotatedSortedArraySearch.java
$ java RotatedSortedArraySearch
7
8 11 13 15 1 4 6
1
Search(1) = 4