Find maximum in sorted and rotated array

Question

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

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. — Mast
– Mast ♦, Commented Oct 29, 2018 at 11:22
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). — Rodrigo
– Rodrigo, Commented Oct 29, 2018 at 17:18
Somebody defaced your question and you accepted it. Please don't. The additional context was helpful and shouln't have been removed. — Mast
– Mast ♦, Commented Oct 29, 2018 at 17:24

vnp · Accepted Answer · 2018-10-28 20:22:21Z

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]);

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. — mdfst13
– mdfst13, Commented Jul 30, 2022 at 23:25

Stack Exchange Network

Find maximum in sorted and rotated array

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Find maximum in sorted and rotated array

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions