Search in a Sorted Rotated Array

Problem

Given an array which is sorted but rotated. Now our task is to search an element in the array. [3,4,5,1,2]

Strategy

Since searching a sorted array is faster than unsorted one. We will try to bring this rotated array to initial position and then peform the search.

After we search in the sorted array, we convert the index of sorted array to rotated array.

Algorithm

• Find the index of rotation
• Convert rotated array to sorted array
• Search the element with binary search
• Convert the found index to rotated array index with a formula.

Solution

import java.util.Arrays;

public class RotatedArray{

    public static void main(String[] args) {

        int[] arr = new int[]{3,4,5,1,2};
        int pivot = -1;

        for(int i=0;i<arr.length-1;i++){
            if(arr[i]>arr[i+1]){
                pivot = i+1;
            }
        }

        //Fill up the sorted array
        int[] sorted = new int[arr.length];

        int index = 0;
        //from pivot to end
        for(int i=pivot; i<arr.length;i++)
            sorted[index++] = arr[i];
        //from start to pivot    
        for(int i=0; i<pivot;i++)
            sorted[index++] = arr[i];

        System.out.println(Arrays.toString(arr));

        // System.out.println(Arrays.toString(sorted));

        int pos = Arrays.binarySearch(sorted, Integer.parseInt(args[0]));

        System.out.println("index: " + ( pos + pivot ) % arr.length );

    }

}

Output

The above program takes the element as input and gives out the index of the element.

java RotatedArray 3
index: 0