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.

• rolfl: I have asked another moderator to review this question. It is my opinion that you have completely changed your question by adding details that were not part of the original specification. As a consequence, your edits have completely invalidated my answer. If your edits had included changing the code I would have rolled them back.... but, as I have answered this question, I am not 'objective' enough.
• Xin: @rolfl Is it better to just ask a new question with the added details?

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)....

• Xin: 1. it is not possible to return null in constructor. 2. Added three special cases. 3. It checks for out of bond condition on newLeft and newRight. And there is always at lease one peak in a nonempty array. 4. a static method should be better in this case. Finally, I have run a dozen tests on this code. compareTo should work as it is supposed to.
• andrejb-dev: @rolfl as pragmatic programmer why are you encouraging to use null as return? I think null should be avoided and Null Object pattern used instead, or throw exception as Xin is doing correctly. Next using this as object is far more better than static method. Static methods are hard to extend, object can be extended for example with decorator pattern. More on this can be found here yegor256.com/2015/02/26/composable-decorators.html, but I agree with the bracing of oneliners
• rolfl: @Zavael - your suggestions are ... interesting. Why have you not put it together as an answer?
• andrejb-dev: @rolfl they were not related to the question directly, but more to your answer. And in general I agree with your answer, I couldnt come up with anything else that would add to this :)

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.

• SuperBiasedMan: Welcome to Code Review! Whilst this may theoretically be helpful for the OP, it would be preferable to include the relevant parts of the links here while detailing their use for the OP. You can still provide the link for reference.