# Find maximum in sorted and rotated array

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
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). 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
Oct 29, 2018 at 17:24

## 1 Answer

• 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. Jul 30, 2022 at 23:25