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.
Comments
Post a Comment
Leave Comment