Find Maximum Element in a Bitonic Array - Java Solution

1. Introduction

In this blog post, we'll solve the problem of finding the maximum element in a bitonic array. A bitonic array is an array that first increases to a maximum point and then decreases.

Problem

Given a bitonic array, which is first increasing and then decreasing, find the maximum value in the array.

2. Solution Steps

1. Use a modified binary search to find the maximum element.

2. If the mid element is greater than both its neighbors, return it as the maximum.

3. If the mid element is smaller than the next element, search in the right half.

4. If the mid element is smaller than the previous element, search in the left half.

5. Handle the edge cases where the array is strictly increasing or decreasing.

3. Code Program

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] a1 = {2, 4, 6, 8, 10, 3, 1};
        System.out.println("Maximum: " + findBitonicMax(a1));

        int[] a2 = {3, 23, 10, 8, 7, 6};
        System.out.println("Maximum: " + findBitonicMax(a2));

        int[] a3 = {10, 20, 30, 40, 50};
        System.out.println("Maximum: " + findBitonicMax(a3));

        int[] a4 = {100, 80, 60, 40, 20, 0};
        System.out.println("Maximum: " + findBitonicMax(a4));
    }

    // Method to find the maximum in a bitonic array
    public static int findBitonicMax(int[] a) {
        int start = 0, end = a.length - 1;

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

            if (mid > 0 && mid < a.length - 1) {
                if (a[mid] > a[mid - 1] && a[mid] > a[mid + 1]) {
                    return a[mid]; // Maximum found
                } else if (a[mid - 1] > a[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else if (mid == 0) {
                return a[0] > a[1] ? a[0] : a[1];
            } else if (mid == a.length - 1) {
                return a[mid];
            }
        }
        return -1;
    }
}

Output:

Maximum: 10
Maximum: 23
Maximum: 50
Maximum: 100

Explanation:

The findBitonicMax method performs a binary search to find the maximum element in the bitonic array. It checks if the mid element is greater than both its neighbors. If so, it's the maximum. Otherwise, it searches in the half of the array where the sequence is increasing. 

The method efficiently finds the maximum element, handling different scenarios, including edge cases like strictly increasing or decreasing arrays.