1
\$\begingroup\$

This is an interview question. A sorted rotated array is a sorted array which was rotated 0 or more times.

For example: [1,2,3] -> [2,3,1]

Please tell me what do you think about the following (correctness, efficiency, coding conventions) and specifically if I can remove in some way the special handle for array of two elements:

static int findMax(int arr[]) { 
    return findMax(arr, 0 , arr.length - 1); 
} 

static int findMax(int arr[], int low, int high) {
    int middle;

    if (low == high) {
        return arr[low];
    }
    if ( Math.abs(high - low) == 1 ) {
        return Math.max(arr[low], arr[high]);
    }

    middle = (low + high) >> 1;
    if (arr[middle] > arr[middle + 1]) {
        return arr[middle];
    }
    if (arr[low] > arr[middle]) {
        return findMax(arr, low, middle - 1);
    }
    return findMax(arr, middle + 1, high);
}  
\$\endgroup\$
3
  • \$\begingroup\$ Welcome to Code Review! Have you tested this? How? Does it pass your tests? What made you write this? Please add more context. More context => better questions => better answers. \$\endgroup\$
    – Mast
    Oct 29, 2018 at 11:22
  • \$\begingroup\$ Yes, I wrote some nine tests which passed (different array cases). I wrote that because it's an interview question I saw in some site (preparation for an interview). \$\endgroup\$
    – Rodrigo
    Oct 29, 2018 at 17:18
  • \$\begingroup\$ Somebody defaced your question and you accepted it. Please don't. The additional context was helpful and shouln't have been removed. \$\endgroup\$
    – Mast
    Oct 29, 2018 at 17:24

1 Answer 1

2
\$\begingroup\$
  • Math.abs in Math.abs(high - low) == 1 is suspicious. high should always be not less than low. Remove it.

  • middle = (low + high) >> 1 may (and will) overflow. Do middle = low + (high - low) >> 1.

    That said, >> 1 is no better than) / 2.

  • Java is notorious in not eliminating the tail recursion. You should do it manually. First, rewrite it in a tail-recursive form:

        if (low == high) {
            return arr[low];
        }
        if ( Math.abs(high - low) == 1 ) {
            return Math.max(arr[low], arr[high]);
        }
    
        middle = (low + high) >> 1;
        if (arr[middle] > arr[middle + 1]) {
            return arr[middle];
        }
        if (arr[low] > arr[middle]) {
            high = middle - 1;
        } else {
            low = middle + 1;
        }
        return findMax(arr, low, high);
    

    then eliminate a recursive call:

        while (high - low > 2) {
            middle = low + (high - low) / 2;
            if (arr[middle] > arr[middle + 1]) {
                return arr[middle];
            }
            if (arr[low] > arr[middle]) {
                high = middle - 1;
            } else {
                low = middle + 1;
            }
        }
        return Math.max(arr[low], arr[high]);
    
\$\endgroup\$
1
  • \$\begingroup\$ This should have while (high - low >= 2) {. Consider a three element array. So low is 0 and high is 2; your code would return Math.max(arr[0], arr[2]); without ever entering the body of the loop. And frankly, I think that's overcomplicating things. The code works fine with while (high > low) { and return arr[low];. No 2 or Math.max needed. \$\endgroup\$
    – mdfst13
    Jul 30, 2022 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.