finding 1D peak of a given array

Question

I am writing the code for peak finding algorithm for a 1D array. I have read this post Peak finding algorithm. This is exactly what I am trying to do, there is discussion about time complexity but nothing of sort of pseudocode. The problem:

Given an array [a,b,c,d,e,f,g] where a to g are numbers, b is a peak if and only if a<=b and b>=c.

Example: given an array {1,2,3,4,5,19,25,20}, index 6 should be returned. The edge cases should give:

{100,4,3,1,19,20} -- index 0

{1,3,5,19,20} -- index 4

I have implemented in Java. my current run-time is O(n). I am wondering if this could be improved

public static int naive(int[] arr){
        int l=arr.length;
        if (arr[0]>=arr[1]) {
            return 0;
        }
        if (arr[l-1]>arr[l-2]){
            return l-1;
        }
        for (int i=1; i < arr.length-1;i++){
             if (arr[i] >= arr[i-1] && arr[i] >= arr[i+1] ){
                 return i;
             }
        }
        return -1;
    }

Answer 1

The following function is probably a tiny bit more efficient than yours. Note that this will find a local maximum.

    public static int findLocalMaximum(int[] arr){
        int i = 0;
        while(i + 1 < arr.length && arr[i+1] >= arr[i]) {
            ++i;
        }
        return i;
    }

Edit: The following function finds peaks as defined in the question. Note that I removed the boundary check in the while loop, as the loop will only be reached if arr[l-2] > arr[l-1], an so the condition in the while loop will be false and l-2 will be returned.

    public static int findPeak(int[] arr){
        int l = arr.length;
        if(arr[0] >= arr[1]) {
            return 0;
        }

        if(arr[l-1] >= arr[l-2]) {
            return l-1;
        }

        int i = 1;
        while(arr[i+1] > arr[i]) {
            ++i;
        }
        return i;
    }

Answer 2

If I may propose my solution:

public static int findPeak(int[] array, int start, int end) {
    int index = start + (end - start) / 2;

    if (index - 1 >= 0 && array[index] < array[index - 1]) {
        return findPeak(array, start, index - 1);
    } else if (index + 1 <= array.length - 1 && array[index] < array[index + 1]) {
        return findPeak(array, index + 1, end);
    } else {
        return array[index];
    }
}

I think it is simpler to handle edge cases directly in the if statements. I also tested with a couple of inputs and it seems to work.

Answer 3

A binary search-like algorithm should work. That employs divide and conquer strategy. since you are interested in single peak, the best you can do is O(log n). But if you want to find all peaks, it will be O(n) atleast.

Here is the divide-and conquer algorithm:

public static int peak1D(int[] arr, int start, int end){
          //edge cases
        if (end-start==1){
            if (start==0)
                return start;
            else 
             return end;
        }
        int i = start+end>>>1;
        if (arr[i]<arr[i-1])
           return peak1D(arr,start,i);
        if (arr[i]<arr[i+1]){
            return peak1D(arr, i, end);
        }
        else
            return i;
    }

I tested with a couple of inputs and it seems to work. my handling of edge cases is not great. though it is simple reasoning

Answer 4

Assume Array is global for simplicity you can pass it if you want.

    private static int getPeak1D(int start,int end)
{
    int x = (start+end)/2;

    if(     (x == 0 && array[x] >= array[x+1]) ||
            (x == array.length-1 && array[x]>=array[x-1]) ||
            (x>0 && x< array.length-1 && array[x] >= array[x-1] && array[x] >= array[x+1]))
        return x;

    if(x+1 < array.length && array[x] < array[x+1])
        temp =  getPeak1D(x+1,end);

    if(temp > -1)
        return temp;

    if(x-1 > -1 && array[x] < array[x-1])
        return getPeak1D(0,x-1);
    else
        return -1;
}

The First if check first edge, second edge, and inner part for peaks. if no peaks are found, if array[x+1] > array[x], The Second if will go to the right half of the array. we store it in temp (i have it as global) we dont return it because in case both array[x+1] and array[x-1] are both bigger than array[x] but the right side didn't find any peaks you should go to the third if to check the left side

Check this for the logic behind it https://courses.csail.mit.edu/6.006/spring11/rec/rec02.pdf