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
start
index is greater than theend
index - if the
mid
element is greater than its next updated end index, else update the start index. - in the
end
, thestart
andend
indexes 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()
}