Find Peak element in Mountain Array or Bitonic Array

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

  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 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()
}

 

follow us on