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

• Mast: 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.
• Rodrigo: 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).
• Mast: Somebody defaced your question and you accepted it. Please don't. The additional context was helpful and shouln't have been removed.

Answer 1

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

• mdfst13: 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.