Example 1:
Input: arr = {5, 10, 15, 12, 8, 3}
Output: 15
This instance demonstrates an array that initially increases from 5 to 15 before decreasing, with the peak value capped at 15.
Example 2:
Input: arr = {2, 4, 6, 10, 8, 5, 3}
Output: 10
In this instance, a sequence ascends from 2 to 10 before descending, reaching a peak of 10.
Example 3:
Input: arr = {1, 2, 3, 4, 5, 4, 3, 2, 1}
Output: 5
Here, we are employing various approaches to address this issue. The methods include:
Method 1: Linear Search
While iterating through the array, it is possible to maintain a record of both the highest value and the elements. Subsequently, the method concludes by presenting the most significant element.
Program:
#include <stdio.h>
// Function to find the maximum element using linear search
int findMaximum(int arr[], int n) {
if (n <= 0) {
// Handle the case of an empty array
return -1; // Return a special value to indicate an error or no maximum
}
int max = arr[0]; // Initialize max with the first element of the array
// Traverse the array to find the maximum element
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i]; // Update max if a larger element is found
}
}
return max;
}
int main() {
int arr[] = {12, 45, 67, 89, 34, 56};
int n = sizeof(arr) / sizeof(arr[0]);
int maximum = findMaximum(arr, n);
if (maximum != -1) {
printf("The maximum element is %d\n", maximum);
} else {
printf("The array is empty.\n");
}
return 0;
}
Output:
The maximum element is 89
Method 2: Using the Binary Search - Recursive Solution
In this function, we identify the maximum element in a dynamically changing array by employing binary search technique.
The following are some ways to change the traditional binary search methodology:
- The mid element is the maximum if it is larger than both of its adjacent elements.
- We should attempt to search on the right half of the array if the mid member is smaller than its subsequent element. Decide that low equals mid plus 1. Array example: 2, 4, 6, 8, 10, 3,
- Similar to this, we should try to search on the left side if the mid element is larger than the following element. Decide that high = mid - 1. Array example: 3, 50, 10, 9, 7, 6.
Program:
#include <stdio.h>
// Function to find the maximum element using binary search (recursive)
int findMaximum(int arr[], int low, int high) {
// Base case: If there's only one element in the array
if (low == high) {
return arr[low];
}
// Calculate the middle index
int mid = (low + high) / 2;
// If the middle element is greater than the next element and smaller than the previous element,
// it is the maximum element
if (arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1]) {
return arr[mid];
}
// If the middle element is greater than the next element and smaller than the previous element,
// the maximum lies on the left side of mid
if (arr[mid] > arr[mid + 1] && arr[mid] < arr[mid - 1]) {
return findMaximum(arr, low, mid - 1);
}
// Otherwise, the maximum lies on the right side of mid
return findMaximum(arr, mid + 1, high);
}
int main() {
int arr[] = {10, 20, 30, 40, 50, 30, 20};
int n = sizeof(arr) / sizeof(arr[0]);
int maximum = findMaximum(arr, 0, n - 1);
printf("The maximum element is %d\n", maximum);
return 0;
}
Output:
The maximum element is 50
Explanation:
In this instance, the findMaximum function employs recursive binary search to determine the highest value in the array. Subsequently, the main function displays the maximum element, which is 50.
Method 3: Finding the largest member in an array that is expanding and decreasing iteratively using binary search.
The following changes can be made to the typical binary search method:
- The mid element is the maximum if it is larger than both of its adjacent elements.
- We should attempt to search on the right half of the array if the mid member is smaller than its subsequent element. Make low = mid + 1 as a result. Array example: 2, 4, 6, 8, 10, 3,
- Similar to this, we should try to search on the left side if the mid element is larger than the following element. Decide that high = mid - 1. Array example: 3, 50, 10, 9, 7, 6.
C++ Program:
#include <iostream>
using namespace std;
int maxInBitonic(int arr[], int low, int high) {
// Find out the size of the array for edge case checking
int n = high + 1;
while (low <= high) {
// Find the mid
int mid = low + (high - low) / 2;
// If mid index value is the maximum
if (arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1]) {
return arr[mid];
}
// Reduce search space by moving to the right
else if (arr[mid] < arr[mid + 1]) {
low = mid + 1;
}
// Reduce search space by moving to the left
else {
high = mid - 1;
}
}
// Return the maximum element found
return arr[high];
}
int main() {
int arr[] = { 10, 30, 40, 50, 60, 20 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The maximum element is " << maxInBitonic(arr, 0, n - 1) << endl;
return 0;
}
Output:
The maximum element is 60
Explanation:
In this instance, the maxInBitonic method identifies the highest value within a bitonic array through an iterative binary search technique. Subsequently, the primary function displays the maximum element, which in this case is 60.
Method 4: Stacking
- In this method, make an empty stack to store the array element indices.
- Go through the array in a left-to-right direction until we locate the most elements. As long as the element is less than or equal to the one before it, push the index of each element onto the stack.
- When an element is discovered that is bigger than the one before it, we know that the maximum element has been found. After that, until we discover an index whose corresponding element is bigger than the current element, we can pop all the indices from the stack.
- The highest element is the one that corresponds to the stack's final index.
C++ Program:
#include <bits/stdc++.h>
using namespace std;
int findMax(int arr[], int n) {
stack<int> s;
int max = 0;
for (int i = 0; i < n; i++) {
if (s.empty() || arr[i] <= arr[s.top()]) {
s.push(i);
} else {
while (!s.empty() && arr[i] > arr[s.top()]) {
int index = s.top();
s.pop();
if (arr[index] > max) {
max = arr[index];
}
}
s.push(i);
}
}
while (!s.empty()) {
int index = s.top();
s.pop();
if (arr[index] > max) {
max = arr[index];
}
}
return max;
}
int main() {
int arr[] = { 7, 10, 3, 2, 8, 15, 20 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The maximum element is " << findMax(arr, n) << endl;
return 0;
}
Output:
The maximum element is 20