Search in a sorted rotated array

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;
    }
}

Comments

Post a Comment

Popular posts from this blog

First Non-Repeated Character

Question:  Write an algorithm to find the first non-repeated character in a string. For example, the first non-repeated character in the string ‘abcdab’ is ‘c’. Answer:  Seems trivial enough right? If a character is repeated, we should be able to search the string to determine if that character appears again. So if we go about doing this for every character in the string, our worst case run time would O(n^2). Here is some code to show this logic. char returnFirstNonRepeatedChar( char * str ) { int i, repeated = 0; int len = strlen(str); for( i = 0; i < len; i++ ) { repeated = 0; for( j = 0; j < len; j++ ) { if( i != j && str[i] == str[j] ) { repeated = 1; break; } } if( repeated == 0 ) { // Found the first non-repeated character return str[i]; } } return ''; } This approach seems to work perfectly well. But
Read more

Pick a Random Byte

Question:  You have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal. Answer:  Since we can only store one byte at a time, we have to be able to work with the bytes as they come in. We can’t store everything, count the number of bytes and pick one. That would be too easy wouldn’t it? Let’s think it through. We don’t know how many bytes there are, so at any point in time we should have a random byte picked from all the bytes we have seen so far. We shouldn’t worry about the total number of bytes at any time. When we get the first byte, it is simple. There is only one so we store it. When we get the second one, it has 1/2 probability of being picked and the one we have stored has a 1/2 probability of being picked (we can use any programming language’s built-in random function). After pick
Read more