fork download
copy 
  1. class RotatedIntArray {
  2.  
  3.     int[] arr;
  4.     public RotatedIntArray(int[] arr) {
  5.         this.arr = arr;
  6.     }
  7.  
  8.     // We need to find a rotation point in the array
  9.     // i.e. arr[n] > arr[n+1].
  10.     // Then we know that arr[n+1] is the minimum.
  11.     public int findMin() {
  12.         int low  = 0;
  13.         int high = arr.length-1;
  14.  
  15.         while (arr[low] > arr[high]) {
  16.             int mid = (low + high) >>> 1; // prevent overflow for large values
  17.             if (arr[mid] > arr[high]) { 
  18.                 low = mid+1; // rotation point is between mid and high
  19.             } else {
  20.                 high = mid;  // rotation point is between low and mid
  21.             }
  22.         }
  23.         return low;
  24.     }
  25.  
  26.     public int findKey(int key) {
  27.         int minIndex = findMin(); // O(log n)
  28.         if (key > arr[(arr.length-1)]) {
  29.             return binarySearch(key, 0, minIndex-1); // O(log n)
  30.         } else {
  31.             return binarySearch(key, minIndex, arr.length-1); // O(log n)
  32.         }
  33.     }
  34.  
  35.     // Standard binary search for non-rotated array
  36.     public int binarySearch(int key, int low, int high) {
  37.         while (low <= high) {
  38.             int mid = (low + high) >>> 1; // prevent overflow for large values
  39.             if (key == arr[mid]) {
  40.                 return mid;
  41.             } else if (arr[mid] > key) {
  42.                 high = mid-1;
  43.             } else {
  44.                 low = mid+1;
  45.             }
  46.         }
  47.         return -1;
  48.     }
  49.  
  50.     //Helper methods for testing
  51.     public void rotate() {
  52.         int[] copy = new int[arr.length];
  53.         for (int i=0; i<arr.length; i++) {
  54.             copy[i] = arr[i];
  55.         }
  56.         for (int i=0; i<arr.length-1; i++) {
  57.             arr[i] = copy[i+1];
  58.         }
  59.         arr[arr.length-1] = copy[0];
  60.     }
  61.  
  62.     public String toString() {
  63.         String s = "";
  64.         for (int i=0; i<arr.length; i++) {
  65.             s += arr[i] + ",";
  66.         }
  67.         s += "\n";
  68.         return s;
  69.     }
  70.  
  71.     public static void main(String[] args) {
  72.  
  73.         int[] odd  = {1,2,3,4,5,6,7,8,9};
  74.         int[] even = {2,25,40,51,733,748};
  75.  
  76.         RotatedIntArray testOdd = new RotatedIntArray(odd);
  77.         RotatedIntArray testEven = new RotatedIntArray(even);
  78.  
  79.         System.out.println("Testing with a array of odd length:");
  80.         for (int i=0; i<9; i++) {
  81.             System.out.print("Array: " + testOdd);
  82.  
  83.             System.out.print("Minimum of the array is at the index ");
  84.             System.out.println(testOdd.findMin());
  85.             for (int j=1; j<10; j++) {
  86.                     System.out.print("Searching for key " + j + " in the array: ");
  87.                     System.out.println(testOdd.findKey(j));
  88.             }
  89.             testOdd.rotate();
  90.             System.out.println();
  91.         }
  92.  
  93.         System.out.println("\n----------------\n");
  94.         System.out.println("Testing with a array of even length:");
  95.  
  96.         for (int i=0; i<6; i++) {
  97.             System.out.print("Array: " + testEven);
  98.  
  99.             System.out.print("Minimum of the array is at the index ");
  100.             System.out.println(testEven.findMin());
  101.             for (int j=0; j<6; j++) {
  102.                 int key = even[j];
  103.                     System.out.print("Searching for key " + key + " in the array: ");
  104.                     System.out.println(testEven.findKey(key));
  105.             }
  106.             testEven.rotate();
  107.             System.out.println();
  108.         }
  109.     }
  110. }
Success #stdin #stdout 0.08s 380480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Testing with a array of odd length:
Array: 1,2,3,4,5,6,7,8,9,
Minimum of the array is at the index 0
Searching for key 1 in the array: 0
Searching for key 2 in the array: 1
Searching for key 3 in the array: 2
Searching for key 4 in the array: 3
Searching for key 5 in the array: 4
Searching for key 6 in the array: 5
Searching for key 7 in the array: 6
Searching for key 8 in the array: 7
Searching for key 9 in the array: 8

Array: 2,3,4,5,6,7,8,9,1,
Minimum of the array is at the index 8
Searching for key 1 in the array: 8
Searching for key 2 in the array: 0
Searching for key 3 in the array: 1
Searching for key 4 in the array: 2
Searching for key 5 in the array: 3
Searching for key 6 in the array: 4
Searching for key 7 in the array: 5
Searching for key 8 in the array: 6
Searching for key 9 in the array: 7

Array: 3,4,5,6,7,8,9,1,2,
Minimum of the array is at the index 7
Searching for key 1 in the array: 7
Searching for key 2 in the array: 8
Searching for key 3 in the array: 0
Searching for key 4 in the array: 1
Searching for key 5 in the array: 2
Searching for key 6 in the array: 3
Searching for key 7 in the array: 4
Searching for key 8 in the array: 5
Searching for key 9 in the array: 6

Array: 4,5,6,7,8,9,1,2,3,
Minimum of the array is at the index 6
Searching for key 1 in the array: 6
Searching for key 2 in the array: 7
Searching for key 3 in the array: 8
Searching for key 4 in the array: 0
Searching for key 5 in the array: 1
Searching for key 6 in the array: 2
Searching for key 7 in the array: 3
Searching for key 8 in the array: 4
Searching for key 9 in the array: 5

Array: 5,6,7,8,9,1,2,3,4,
Minimum of the array is at the index 5
Searching for key 1 in the array: 5
Searching for key 2 in the array: 6
Searching for key 3 in the array: 7
Searching for key 4 in the array: 8
Searching for key 5 in the array: 0
Searching for key 6 in the array: 1
Searching for key 7 in the array: 2
Searching for key 8 in the array: 3
Searching for key 9 in the array: 4

Array: 6,7,8,9,1,2,3,4,5,
Minimum of the array is at the index 4
Searching for key 1 in the array: 4
Searching for key 2 in the array: 5
Searching for key 3 in the array: 6
Searching for key 4 in the array: 7
Searching for key 5 in the array: 8
Searching for key 6 in the array: 0
Searching for key 7 in the array: 1
Searching for key 8 in the array: 2
Searching for key 9 in the array: 3

Array: 7,8,9,1,2,3,4,5,6,
Minimum of the array is at the index 3
Searching for key 1 in the array: 3
Searching for key 2 in the array: 4
Searching for key 3 in the array: 5
Searching for key 4 in the array: 6
Searching for key 5 in the array: 7
Searching for key 6 in the array: 8
Searching for key 7 in the array: 0
Searching for key 8 in the array: 1
Searching for key 9 in the array: 2

Array: 8,9,1,2,3,4,5,6,7,
Minimum of the array is at the index 2
Searching for key 1 in the array: 2
Searching for key 2 in the array: 3
Searching for key 3 in the array: 4
Searching for key 4 in the array: 5
Searching for key 5 in the array: 6
Searching for key 6 in the array: 7
Searching for key 7 in the array: 8
Searching for key 8 in the array: 0
Searching for key 9 in the array: 1

Array: 9,1,2,3,4,5,6,7,8,
Minimum of the array is at the index 1
Searching for key 1 in the array: 1
Searching for key 2 in the array: 2
Searching for key 3 in the array: 3
Searching for key 4 in the array: 4
Searching for key 5 in the array: 5
Searching for key 6 in the array: 6
Searching for key 7 in the array: 7
Searching for key 8 in the array: 8
Searching for key 9 in the array: 0


----------------

Testing with a array of even length:
Array: 2,25,40,51,733,748,
Minimum of the array is at the index 0
Searching for key 2 in the array: 0
Searching for key 25 in the array: 1
Searching for key 40 in the array: 2
Searching for key 51 in the array: 3
Searching for key 733 in the array: 4
Searching for key 748 in the array: 5

Array: 25,40,51,733,748,2,
Minimum of the array is at the index 5
Searching for key 25 in the array: 0
Searching for key 40 in the array: 1
Searching for key 51 in the array: 2
Searching for key 733 in the array: 3
Searching for key 748 in the array: 4
Searching for key 2 in the array: 5

Array: 40,51,733,748,2,25,
Minimum of the array is at the index 4
Searching for key 40 in the array: 0
Searching for key 51 in the array: 1
Searching for key 733 in the array: 2
Searching for key 748 in the array: 3
Searching for key 2 in the array: 4
Searching for key 25 in the array: 5

Array: 51,733,748,2,25,40,
Minimum of the array is at the index 3
Searching for key 51 in the array: 0
Searching for key 733 in the array: 1
Searching for key 748 in the array: 2
Searching for key 2 in the array: 3
Searching for key 25 in the array: 4
Searching for key 40 in the array: 5

Array: 733,748,2,25,40,51,
Minimum of the array is at the index 2
Searching for key 733 in the array: 0
Searching for key 748 in the array: 1
Searching for key 2 in the array: 2
Searching for key 25 in the array: 3
Searching for key 40 in the array: 4
Searching for key 51 in the array: 5

Array: 748,2,25,40,51,733,
Minimum of the array is at the index 1
Searching for key 748 in the array: 0
Searching for key 2 in the array: 1
Searching for key 25 in the array: 2
Searching for key 40 in the array: 3
Searching for key 51 in the array: 4
Searching for key 733 in the array: 5
https://ideone.com/ykCPxL
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!