Search In Mountain Array

Monotonic arrays are strictly 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

• Find the Peak element in the Mountain array
• Search for the element in the first half of the Mountain array, ie from the start of the array up to the index of the Peak element.
• If the target element is found in the first half of the array, then it's the result, else function will return -1.
• else search for the element in the second half of the Mountain array, ie from the index of the Peak element up to the end of the array.

package org.wesome.dsalgo;

public class SearchInMountainArray {
    public static int orderAgnosticBinarySearch(int[] arr, int find, int start, int end) {
//        find the sort order of the array
        boolean isAsc = arr[start] < arr[end];

        while (start <= end) {
            int mid = start + (end - start) / 2;
            // If the target element is present in the middle itself
            if (arr[mid] == find) {
                return mid;
            }
//            check the sort order of the array
            if (isAsc) {
                // In ascending order sorted array, If the find is smaller than mid-element, then it can only be present in left sub-array
                if (arr[mid] > find) {
                    end = mid - 1;
                }
                // Else the element can only be present in right sub-array
                else {
                    start = mid + 1;
                }
            } else {
                // In descending order sorted array, If the element is smaller than mid-element, then it can only be present in right sub-array
                if (arr[mid] < find) {
                    end = mid - 1;
                }
                // Else the element can only be present in left sub-array
                else {
                    start = mid + 1;
                }
            }
        }
        return -1;
    }

    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 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 start;
    }

    public static int searchInMountainArray(int[] arr, int find) {
//        Find the peak element in the mountain array
        int peakInMountainArray = peakInMountainArray(arr);
//        find the target element in the first half of the array, ie from the start index up to the index of the peak element
        int findInAscendingOrder = orderAgnosticBinarySearch(arr, find, 0, peakInMountainArray);
//        if the element is found in the first half, it the result, else search in the second half of the array, ie from the index of the peak element up to the end of the array
        if (findInAscendingOrder != -1) {
            return findInAscendingOrder;
        } else {
            return orderAgnosticBinarySearch(arr, find, peakInMountainArray + 1, arr.length - 1);
        }
    }
}

package org.wesome.dsalgo;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import static org.wesome.dsalgo.SearchInMountainArray.searchInMountainArray;

public class SearchInMountainArrayTest {
    @Test
    void searchIMountainArrayTest1() {
        int[] arr = new int[]{0, 1, 0, 2, 0, 4, 0, 6, 0};
        int searchIMountainArray = searchInMountainArray(arr, 6);
        Assertions.assertEquals(7, searchIMountainArray);
    }

    @Test
    void searchIMountainArrayTest2() {
        int[] arr = new int[]{1, 2, 3, 4, 5, 4, 3, 2, 1, 0};
        int searchIMountainArray = searchInMountainArray(arr, 0);
        Assertions.assertEquals(9, searchIMountainArray);
    }

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

    @Test
    void searchIMountainArrayTest4() {
        int[] arr = new int[]{1, 2, 1, 3, 5, 6, 4};
        int searchIMountainArray = searchInMountainArray(arr, 7);
        Assertions.assertEquals(-1, searchIMountainArray);
    }
}

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