Given a sorted, rotated collection, find an element in it.

ShiftedBinarySearch.java

/**
 * Given a sorted, rotated collection, find an element in it.
 * Rotated defined as elements shifted x to the right.
 * Example:
 *     sorted array: [1, 2, 3]
 *     rotated x = 2: [2, 3, 1]
 */
public final class ShiftedBinarySearch {

    public static void main(String... args) {
        final int[] shifted = {4, 5, 6, 7, 8, 9, 10, 1, 2, 3};

        final int index = shiftedSearch(shifted, 1);

        System.out.println(index);
        assert index == 7;
    }

    private static int shiftedSearch(int[] source, int key) {
        if (source == null || source.length == 0) {
            throw new IllegalArgumentException();
        }
        return shiftedSearchImpl(source, key, 0, source.length - 1);
    }

    private static int shiftedSearchImpl(int[] source, int key, int low, int high) {
        if (high < low) {
            return -1;
        }

        final int mid = low + ((high - low) / 2);

        if (source[mid] == key) {
            return mid;
        }

        /* check if left half is sorted */
        if (source[low] <= source[mid]) {
            if (source[low] <= key && source[mid] > key) {
                return shiftedSearchImpl(source, key, low, mid - 1);
            }
            else {
                return shiftedSearchImpl(source, key, mid + 1, high);
            }
        }

        /* right half must be sorted */
        else {
            if (source[mid] < key && source[high] >= key) {
                return shiftedSearchImpl(source, key, mid + 1, high);
            }
            else {
                return shiftedSearchImpl(source, key, low, mid - 1);
            }
        }
    }
}