Using a Variant of BinarySearch to Find the Maximum in a Bitonic Array

Question

Here is my code, where a is the array to find the maximum of (each element is distinct). From my perspective, if a[mid] is less than a[mid-1] then the position of the maximum should be in the range of [lo, mid-1]. However, when I implement my idea, the program is endless. The solution is to use [lo, mid] as the next iteration.

My question is: Why shouldn't I use mid-1 instead of mid in Line 9?

First edit: Some people ask why didn't I just sort and choose the first element? Since the problem is to find a key in a bitonic array (where elements ascend first then descend). My solution is to find the maximum of the array, separate it into two parts and respectively use BinarySearch to find the key. If I sort the array I will destroy the original order.

Second edit: add more code in detail and the expected output.

public static int getMaxIndex(int[] a) {
    int hi = a.length - 1;
    int lo = 0;
    while (lo < hi && a[lo] <= a[lo+1]) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] > a[mid-1]) {
            lo = mid;
        } else {
            hi = mid - 1;  // Should be mid, not mid-1, why?
        }
    }
    return lo;
}

public static void main(String[] args) {
    int[] a = {1, 2, 3, 5, 7, 9, 8, 6, 4};  // Bitonic array
    System.out.println(getMaxIndex(a));  // Should be 5 
}

Answer 1

The problem you had was that you were not always changing mid. In your example, at one point lo is 4 and pointing to 7 in the array while hi is 5 and points to 9. In the situation where lo and hi are just 1 apart, mid is set to lo. Here you are comparing a[mid] > a[mid-1]. Problem 1, mid-1 is out of range and in rare cases gives an ArrayIndexOutOfBoundsException. Second, if the condition is true, you set lo to mid, which is the value it already had. You are getting nowhere. You are in an infinite loop.

I tried your method with

    System.out.println(getMaxIndex(new int[] { 3 , 8 })); // Expecting 1

I got java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 2

The solution is in the answer by Horse.