CODEWITHSUNDEEP
javaarraysalgorithm
Jorgovanka
Jorgovanka

Reputation: 79

Peak finding algorithm error

Hello everybody could someone help me with my code

It is a code for peak finding ,if you are wondering what is peak finding

here you go

Given an array of integers. Find a peak element in it. An array element is peak if it is NOT smaller than its neighbors. For corner elements, we need to consider only one neighbor. For example, for input array {5, 10, 20, 15}, 20 is the only peak element. For input array {10, 20, 15, 2, 23, 90, 67}, there are two peak elements: 20 and 90. Note that we need to return any one peak element.

My problem is that my code doesnt find a peak element if it is in first position in array or in last

Here is my code it is fairly simple

    public static void main(String[] args) {



    int [] arr = {1,2,3,4,1,3,3,7,8,2,16};
    peakFinding(arr, 0,arr.length);

}


public static void peakFinding(int [] arr,int start ,int end){
    int mid  = (start+end)/2;



    if(arr[mid]<=arr[mid+1]){
            start = mid;
            end = arr.length;

            peakFinding(arr, start, end);
        }else if(arr[mid]<=arr[mid-1]){

            start = 0;
            end = mid-1;
            peakFinding(arr, start, end);
        }else{
            System.out.println("I have found peak "+arr[mid]);
        }

}

Upvotes: 0

Views: 202

Answers (3)

Li Chao
Li Chao

Reputation: 336

Before answering your question, I feel like the starting part of your peakFinding does not look very good, instead of 

int mid  = (start+end)/2;

which might be problematic if start and end is too big and close to Integer.MAX_VALUE, please try 

int mid = start + (end - start) / 2;

Also if you add some code to validate the input (null check of the array, or start <= end something like that), it would be better.

Now let's talk about your algorithm, it is a binary search. 

public static void peakFinding(int [] arr,int start ,int end){

while(start + 1 < end) {
    int mid = start + (end - start) / 2;
    if(arr[mid] <= arr[mid+1]) {
        start = mid;
    } else if (arr[mid] <= arr[mid-1]) {
        end = mid;
    } else {
        System.out.println(arr[mid]);
        return;
    }
}

if(arr[start] > arr[end]) {
    System.out.println(arr[start]);
} else {
    System.out.println(arr[end]);
}

}

Upvotes: 1

Samuel Renold
Samuel Renold

Reputation: 302

Your program does not find all peaks.

If e.g. the condition arr[mid] <= arr[mid + 1] in the first if clause returns true, this means that a peak is searched only in the right part of the array. The left part of the array is no longer searched, although there could be a peak also in the left side of the array.

Upvotes: 0

Bathsheba
Bathsheba

Reputation: 234715

Given that you only need to find one element, and the choice is arbitrary, consider treating the edges as a special case. Before the call to peakFinding include code of the form

if (arr == null || arr.length < 2){
    /*do nothing, no elements*/
} else if (arr[0] >= arr[1]){
    /*first element is peak*/
} else if (arr[arr.length - 1] >= arr[arr.length - 2]){
    /*last element is peak*/
} else {
    /*call peakFinding*/
}

My first check also fixes a potential bug that you had.

Doing it this way preserves the clarity of the complicated parts of the program.

Finally, consider changing the return type of peakFinding to return the position of the element (return mid;), then the output message will be coded in one place.

Upvotes: 1

Related Questions