Monotonic arrays are sorted in ascending or descending order, but in bitonic or mountain arrays some elements are in ascending order and then descending order. for example
0, 1, 0 here 1 is the peak element, and all elements before 1 are in ascending order, and after 1 is in descending order.
1,2,3,4,5,4,3,2,1 here 5 is the peak element, and all elements before 5 are in ascending order, and after 5 are in descending order.
The Algorithm is simple
- keep running the loop until the
startindex is greater than theendindex - if the
midelement is greater than its next updated end index, else update the start index. - in the
end, thestartandendindexes will point to the largest number.
package org.wesome.dsalgo;
public class PeakInMountainArray {
public static int peakInMountainArray(int[] arr) {
int start = 0, end = arr.length - 1;
while (start < end) {
int mid = start + (end - start) / 2;
// if the middle element is greater than its next element, it means its decreasing part of the array
if (arr[mid] > arr[mid + 1]) {
// mid might be the peak of the array, but there is a possibility that an even higher peak may lie on the left sub-array. so keep the mid also, that's why the end is not equal to mid-1
end = mid;
}
// else middle element is less than its next element, it means its increasing part of the array
else {
// in the above if condition, its already checked that the mid element is greater than mid+1, so don't need to keep mid anymore, hence start will be mid+1
start = mid + 1;
}
}
// in the end, the start index and end index both will point to the largest number
return arr[start];
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import static org.wesome.dsalgo.PeakInMountainArray.peakInMountainArray;
public class PeakInMountainArrayTest {
@Test
void peakInMountainArrayTest1() {
int[] arr = new int[]{0, 1, 0};
int peakInMountainArray = peakInMountainArray(arr);
Assertions.assertEquals(1, peakInMountainArray);
}
@Test
void peakInMountainArrayTest2() {
int[] arr = new int[]{1, 2, 3, 4, 5, 4, 3, 2, 1};
int peakInMountainArray = peakInMountainArray(arr);
Assertions.assertEquals(5, peakInMountainArray);
}
@Test
void peakInMountainArrayTest3() {
int[] arr = new int[]{1, 3, 5, 7, 6, 4, 2, 0};
int peakInMountainArray = peakInMountainArray(arr);
Assertions.assertEquals(7, peakInMountainArray);
}
}
plugins {
id 'java'
id "io.freefair.lombok" version "6.4.1"
}
group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8
configurations {
compileOnly {
extendsFrom annotationProcessor
}
}
repositories {
mavenCentral()
}
dependencies {
testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}
test {
useJUnitPlatform()
}