Question: Implement a search function for a sorted rotated array. Duplicates are allowed. Returning any one of the duplicates is acceptable.

Answer: We can do a binary search with some modified checks.

public int rotatedSearch(int[] values, int start, int end,
                          int x){
    if(values[start] == x){
        return start;
    } else if(values[end] == x){
        return end;
    } else if(end - start == 1) {
        return -1;
    }
    int middle = (start + end) / 2;

    if(values[start] <= values[middle]){
        if(x <= values[middle] && x >= values[start]){
            return rotatedSearch(values, start, middle, x);
        } else {
            return rotatedSearch(values, middle, end, x);
        }
    } else if(values[middle] <= values[end]){
        if(x >= values[middle] && x <= values[end] ){
            return rotatedSearch(values, middle, end, x);
        } else {
            return rotatedSearch(values, start, middle, x);
        }
    } else {
        return -1;
    }
}

Like this question? Follow our feed and tweet it.

Related posts:

1. Sub-Array with the Largest Sum
2. Anagrams in an Array of Strings
3. Permutations of a String