Search code examples
javabinary-search

Why my mid-1 approach is not working in this binary-search question?


I used mid+1 approach to solve this question and it got solved easily but when wanted to solve the same question my changing the comparison form mid+1 to mid-1 it was not working can you help me out where am I wrong?

Problem Link

My Initial approach(mid+1):

class Solution {
public int peakIndexInMountainArray(int[] arr) {
    int start=0;
    int end=arr.length-1;
    
    while(start<=end){
        int mid=start-(start-end)/2;
        if(arr[mid]<arr[mid+1]){
            start=mid+1;
        }
        else {
            end=mid-1;
        }
    }
    return start;
}
}

2nd approach (wrong answer with mid-1 apprach)

class Solution {
public int peakIndexInMountainArray(int[] arr) {
    int start=0;
    int end=arr.length-1;
    
    while(start<=end){
        int mid=start-(start-end)/2;
        if(arr[mid-1]<arr[mid]){
            start=mid+1;
        }
        else {
            end=mid-1;
        }
    }
    return end;
}
}

Solution

  • you should set the start value at 1: int start=0; Because you can now get the mid value to be 0 if the value that you are searching is in the first position of the list (for example the list: 10, 6, 5, 2, 1), the peak value is the first element of the list and when you try to access the arr[mid-1] you ar getting an ArrayIndexOutOfBoundsException.