Question

Consider an array A[1 · · · n] which is sorted and then rotated k steps to the right. For example, we might start with the sorted array [1, 4, 5, 9, 10], and rotate it right by k = 3 steps to get [5, 9, 10, 1, 4]. Give an O(log n)-time algorithm that finds and returns the position of a given element x in array A, or returns None if x is not in A. Your algorithm is given the array A[1 · · · n] but does not know k. Use Java to solve this problem

Answer 1

//Create a new class in any editor

public class RotatedArray {

public static void main(String[] args) {
//pass the sorted array and k value
    int[] array = new int[]{1, 4, 5, 9, 10};
//enter value of k
int k=3;

//enter value to search element
int x=5;


int position= rotateArray(array, k, x);
System.out.println("The element x at position "+position);
}

private static int rotateArray(int[] array, int k, int x) {
int position = -1;

// System.out.println("Original array: ");
// for (int i = 0; i < array.length; i++) {
// System.out.print(array[i] + " ");
// }

for (int i = 0; i < k; i++) {
int j, end;
//Stores the last element of array
end = array[array.length - 1];

for (j = array.length - 1; j > 0; j--) {
//Shift element of array by one
array[j] = array[j - 1];
}
//end element of array will be added to the start of array.
array[0] = end;
}

  
  
for(int i=0;i<array.length;i++)
{
if(array[i]==x)
{
return i;
}
}
// System.out.println();
// System.out.println("Array after right rotation: ");
// for (int i = 0; i < array.length; i++) {
// System.out.print(array[i] + " ");
// }

return position;
}
}

//output

Original array:
1 4 5 9 10
Array after right rotation:
5 9 10 1 4
The element x at position 0