static int rotatedBinarySearch(Integer array[], int key, int start, int end)
    {
        if (start > end)
            return -1;

        int middle = start+(end-start)/2;

        // ****IMPORTANT
        if (array[middle] == key)
            return middle;

        // lower half is sorted
        if (array[start] < array[middle]){ // ****IMPORTANT
            if (key >= array[start] && key < array[middle]) {
                //key in lower sorted half - use normal BS
                return binarySearch(array, key, start, middle - 1);
            }else {
                //System.out.println("key: "+key +" start: " + start + " middle: " + middle + " end: " + end+ " start: " +array[start] + " middle: " + array[middle] + " end: " + array[end]);
                //key in unsorted upper half
                return rotatedBinarySearch(array, key, middle + 1, end);
            }
        }
        // upper is sorted
        else {
            if (key > array[middle] && key <= array[end]) {
                //key in upper sorted half - use normal BS
                return binarySearch(array, key, middle + 1, end);
            }else {
                //System.out.println("key: "+key +" start: " + start + " middle: " + middle + " end: " + end+ " start: " +array[start] + " middle: " + array[middle] + " end: " + array[end]);
                //key in unsorted lower half
                return rotatedBinarySearch(array, key, start, middle - 1);
            }
        }

    }