Geek asks and answers

Finding 1D peak of a given array

I am writing code for the peak search algorithm for a 1D array. I read this post Peak Search Algorithm . This is exactly what I'm trying to do, there is a discussion about time complexity, but nothing like pseudo code. Problem:

Given an array [a,b,c,d,e,f,g]where a- gare numbers, bis a peak if and only if a<=band b>=c.

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

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

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

I implemented in Java. current runtime O(n). I wonder if this can 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;
    }
+3
source share
4 answers

A binary search-like algorithm . divide and conquer. single peak, , , O(log n). , O(n) .

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

, , . .

0

, , , . , .

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

: , . , while, , arr[l-2] > arr[l-1], while l-2 .

    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;
    }
+2

:

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

, if. , , .

+1

, Array , , .

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

, , . , [x + 1] > array [x], , . temp ( ), , , [x + 1] [x-1] , [x], ,

, https://courses.csail.mit.edu/6.006/spring11/rec/rec02.pdf

0

More articles:


All Articles