Find Any Peak element in Multiple Mountain Array or K Sorted Mountain Array

Monotonic arrays are sorted in ascending or descending order such as 
1, 2, 3, 4, 5 or 5, 4, 3, 2, 1
Bitonic or Mountain arrays have elements in ascending order and then descending order such as
0, 1, 0 here 1 is the peak element
1, 2, 3, 4, 5, 4, 3, 2, 1 here 5 is the peak element

K Sorted Mountain Array have multiple Monotonic arrays upto K times such as
0, 1, 0, 2, 0, 4, 0, 6, 0 here 1,2,4 and 6 are peak elements
1, 2, 1, 3, 5, 6, 4 here 2 and 6 both are peak element

The Algorithm is simple

  1. keep running the loop until the start index is greater than the end index
  2. if the mid element is greater than its next updated end index, else update the start index.
  3. in the end, the start and end indexes will point to the largest number.
package org.wesome.dsalgo;

public class KSortedMountainArray {
    public static int peakInKSortedMountainArray(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 array's peak, 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, it already checked that mid-element is greater than mid+1, so we 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.KSortedMountainArray.peakInKSortedMountainArray;

public class KSortedMountainArrayTest {
    @Test
    void peakInKSortedMountainArrayTest1() {
        int[] arr = new int[]{0, 1, 0, 2, 0, 4, 0, 6, 0};
        int peakInKSortedMountainArray = peakInKSortedMountainArray(arr);
        Assertions.assertEquals(6, peakInKSortedMountainArray);
    }

    @Test
    void peakInKSortedMountainArrayTest2() {
        int[] arr = new int[]{1, 2, 3, 4, 5, 4, 3, 2, 1};
        int peakInKSortedMountainArray = peakInKSortedMountainArray(arr);
        Assertions.assertEquals(5, peakInKSortedMountainArray);
    }

    @Test
    void peakInKSortedMountainArrayTest3() {
        int[] arr = new int[]{1, 3, 5, 7, 6, 4, 2, 0};
        int peakInKSortedMountainArray = peakInKSortedMountainArray(arr);
        Assertions.assertEquals(7, peakInKSortedMountainArray);
    }

    @Test
    void peakInKSortedMountainArrayTest4() {
        int[] arr = new int[]{1, 2, 1, 3, 5, 6, 4};
        int peakInKSortedMountainArray = peakInKSortedMountainArray(arr);
        Assertions.assertEquals(6, peakInKSortedMountainArray);
    }
}
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()
}

follow us on