Implementation of peak finder

Question

I implemented this peak finder for practice. I have tested it. Everything looks pretty good to me. Please let me know if there is any improvement I can make.

Peak Finder

Let input be an array. input[i] is a peak if input[i] >= input[i + 1] and input[i] >= input[i - 1].

Implement a recursive algorithm of time complexity \$O(\log{n})\$ to find a peak.

class PeakFinder <E extends Comparable<? super E>>{
  private E[] array;

  public PeakFinder(E[] array){
    if(array == null || array.length == 0)
      throw new IllegalArgumentException("array cannot be null or 0");
    this.array = array;
  }

  public E find(){
    return findUtil(0, array.length - 1);
  }

  private E findUtil(int left, int right){
      int mid = (right - left)/2 + left;
      int newLeft = mid + 1;
      int newRight = mid - 1;

      if(newLeft <= right && array[newLeft].compareTo(array[mid]) > 0)
        return findUtil(newLeft, right);
      else if(newRight >= left && array[newRight].compareTo(array[mid]) > 0)
        return findUtil(left, newRight);
      else
        return array[mid];
  }
}

An array always has at least one peak if it is not null or empty.

Special cases:

1. input[i] is a peak if input[i] >= input[i+1] when input[i] is the first element in the array.
2. input[i] is a peak if input[i] >= input[i-1] when input[i] is the last element in the array.
3. input[i] is a peak if input[i] is the only element in the array.

Answer 1

Your code is pretty good. It has elements in it which are relatively sophisticated too. For example, the recursion is clear, and the midpoint function is "right" (that needs an explanation - there's a 'well known' midpoint bug that many midpoint calculations have, but yours does not).

I prefer 1-liner code to be braced, and yours is not. That's disappointing, because I don't like reviews that focus on that only.... but that's really all I can find wrong with your code style.

There are a number of technical problems though.

1. why throw an exception for an empty array? Why not return null?
2. you have not followed the instructions correctly... it is impossible for a 0, 1, or 2 element array to actually have a peak, since there is no i - 1 or i + 1 to compare against. Additionally, there is no peak in cases like [3, 2, 2, 3], since the 2's are not peaks, and the three's are at the edges.
3. your first if conditions are newLeft <= right and newRight >= left, and those are just messy.... your findUtil should have a recursion-terminating condition if (right < left) { return null; } and not spread it around in the method.

4. I am a pragmatist about OOP in Java... Objects are great, I agree, but there is no reason to have an instance for this code. A static method passing the input array in would be fine....:

   public <E extends Comparable<? super E>> E findPeak(E[] data) { ....
   

Finally, about the algorithm. I am not convinced that it works... I have not run it, but I am pretty sure that the compareTo methods are the wrong way around... they should be < 0 and not > 0)....

Answer 2

Your code is working fine. The algorithm can be modified to avoid recursion. Also, instead of throwing an exception, you can return null. Recursion and exceptions are expensive so they should be avoided wherever unnecessary.

Here is a video solution on finding a peak element in an array (iterative). You can also check this link.