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

bitonic array

The numbers are strictly increasing and after an index, the numbers are strictly decreasing

eg: [15, 20, 26, 5, 1]

If the array contains only unique elements, then maximum can be found using following conditions

1. iterate while left index < right index
2. compute middle index (towards left incase no single middle index)
3. if the value at middle is smaller than next element, then move towards right
4. else move left towards left

arr[mid] < arr[mid + 1] will never throw out of bounds exception as left < right invariant is maintained on the loop. hence mid(index) will always be lesser than right(index) and hence there is atleast one index after mid

int left = 0, right = arr.length - 1;
while (left < right) {
  int mid = left + (right - left) / 2;
  if (arr[mid] < arr[mid + 1]) {
    left = mid + 1;
  } else {
    right = mid;
  }
}
return arr[left]; // or arr[right]

              15        20        26         5         1
l=0, r=4      l                   m                    r
m=2

a[m] > a[m+1] l                   r                  
so, r=m

l=0, r=2      l         m         r
m=1

a[m] < a[r+1]                      l,r
m=l+1

Now exit while loop l == r and return value at l or r

Analysis of OP's code

1. A simple reproducible example is [1, 2] - this will cause lo to be stuck to same index and causes infinite loop.
2. Any dataset that reduces to lo + 1 == hi and arr[lo] < arr[hi] will set mid to lo (lo + (hi - lo) / 2 will be lo) and hence the assignment lo = mid causes an infinite loop

Answer 2

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.

Answer 3

Here, the word bitonic means, array is sorted in increasing order, and after some point (may be) it starting to decrease.

Likewise, you have to find the pivot point where array is starting to decrease (if it is exist), if you can able to find the point, that's it, this pivotal point is your answer.

so i am attaching some input/output sequence to make it more clear:

{1, 2, 3, 5, 7, 9, 8, 6, 4}; --> should  return 5 (index at which element is maximum)
{15, 20, 26, 5, 1} --> should return 2 (index at which element is maximum)
{0, 1, 2, 3} --> should return 3 (index at which element is maximum)

now you have to modify your code like following:

public static int getMaxIndex(int[] arr) {
    int  left = 0, right = arr.length - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if(mid == 0 || mid == arr.length-1) {
            // if no such pivotal point exist in sequence/array
            return mid;
        }else if(arr[mid] > arr[mid+1] && arr[mid] > arr[mid-1]){               
            // it's the pivotal point, where element at left side smaller and element at right side too
            return mid;
        }
      if (arr[mid] < arr[mid + 1]) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    return -1;
}