# RotatedSortedArray.java

Below is the syntax highlighted version of RotatedSortedArray.java from §1.4 Analysis of Algorithms.

```/******************************************************************************
*  Compilation:  javac RotatedSortedArray.java
*  Execution:    java RotatedSortedArray N
*  Dependencies: StdOut.java
*
*  Find the a key in a rotated sorted array of N distinct keys.
*
*  We provide two algorithms that solve the problem in logarithmic time.
*
*   - The first algorithm begins by finding the amount k by which the
*     original sorted array was rotated using a variant of binary search.
*     This divides the array into two sorted subarrays b[0..k) and b[k..N).
*     Then, it searches for the key using standard binary search in
*     one of the two subarrays.
*
*   - The second algorithms search for the key x without directly finding
*     the crossover point, using a variant of binary search.
*
*  Note: it is crucial that the array has distinct keys. Otherwise, the
*  problem cannot be solved in logarithmic time (consider an array of
*  all 0s and one 1 in the interior).
*
******************************************************************************/

import java.util.Arrays;

public class RotatedSortedArray {

// rotate the array k to the right
public static int[] rotate(int[] a, int k) {
int N = a.length;
if (k < 0 || k >= N) throw new RuntimeException("illegal value of k");
int[] b = new int[N];
for (int i = 0; i < N; i++) {
b[i] = a[(i - k + N) % N];
}
return b;
}

// sorted array of length N containing 1, 3, 5, ..., 2N-1
public static int[] sortedArray(int N) {
int[] a = new int[N];
for (int i = 0; i < N; i++) {
a[i] = 2*i + 1;
}
return a;
}

// is x in the sorted array a[]?
public static boolean searchInSortedArray(int[] a, int x) {
return Arrays.binarySearch(a, x) >= 0;
}

// return index k of smallest key (unique index for which b[k] < b[k-1])
private static int findMinimumIndex(int[] b) {
int N = b.length;
if (N <= 1) return 0;          // array of length 0 or 1
if (b[0] < b[N-1]) return 0;   // already sorted

// invariant b[lo] > b[hi]
int lo = 0, hi = N-1;
while (true) {
if (hi == lo+1) return hi;
int mid = lo + (hi - lo) / 2;
if      (b[mid] < b[hi]) hi = mid;
else if (b[mid] > b[hi]) lo = mid;
}
}

// is x in the rotated sorted array b[]?
public static boolean searchInRotatedSortedArray1(int[] b, int x) {
int N = b.length;
int k = findMinimumIndex(b);
if (k == 0)         return Arrays.binarySearch(b, x) >= 0;
else if (x >= b[0]) return Arrays.binarySearch(b, 0, k, x) >= 0;
else                return Arrays.binarySearch(b, k, N, x) >= 0;
}

// is x in the rotated sorted array b[]?
public static boolean searchInRotatedSortedArray2(int[] b, int x) {
int N = b.length;
int lo = 0, hi = N-1;
while (true) {
if (hi < lo) return false;
int mid = lo + (hi - lo) / 2;
if (b[mid] == x) return true;
if      (b[lo] <= x && x < b[mid]) return Arrays.binarySearch(b, lo, mid, x) >= 0;
else if (b[mid] < x && x <= b[hi]) return Arrays.binarySearch(b, mid+1, hi+1, x) >= 0;
else if (b[mid] < b[hi]) hi = mid - 1;
else                     lo = mid + 1;
}
}

public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
int[] a = sortedArray(N);

// test all rotations
for (int k = 0; k < N; k++) {
int[] b = rotate(a, k);

// test all search keys
for (int x = 0; x <= 2*N; x++) {

boolean result  = searchInSortedArray(a, x);
boolean result1 = searchInRotatedSortedArray1(b, x);
boolean result2 = searchInRotatedSortedArray2(b, x);
if ((result != result1) || (result != result2)) {
StdOut.println("   - a[] = ");
StdOut.print("     ");
for (int i = 0; i < N; i++)
StdOut.printf("%2d ", a[i]);
StdOut.println();
StdOut.println("   - k   = " + k);
StdOut.println("   - b[] = ");
StdOut.print("     ");
for (int i = 0; i < N; i++)
StdOut.printf("%2d ", b[i]);
StdOut.println();
StdOut.println("   - x         = " + x);
StdOut.println("   - searchInSortedArray(a, x)          = " + result);
StdOut.println("   - searchInRotatedSortedArray1(b, x)  = " + result1);
StdOut.println("   - searchInRotatedSortedArray2(b, x)  = " + result2);
StdOut.println();
}
}
}
}
}

```

Copyright © 2000–2017, Robert Sedgewick and Kevin Wayne.
Last updated: Fri Oct 20 12:50:46 EDT 2017.