Search in Sorted Rotated 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
Sorted Rotated Arrays are a special case of Monotonic arrays. Elements are in sorted order, either ascending or descending but few elements are moved from end to start in the same order. for example

The Algorithm is simple

1. Find mid of the array
2. Check If the target element is present in the middle itself
3. If the mid is greater than or equal to the start, then from mid, the left part of the array is sorted,
   for example, 3, 4, 5, 1, 2 here mid is 5 and greater than the start ie 3, it states that the left of 5 is sorted.
4. if the target is greater than the start but less than mid, it lies between the start and mid, search on the left side of the array, for example
   3, 4, 5, 1, 2 here mid is 5 and the target is 4, the target is less than mid but greater than the start ie 3
5. else the target is greater than mid, it should be the right side of the array, for example
   3, 4, 5, 1, 2 here mid is 5 and target is 1, the target is less than end ie 2 but greater than mid
6. Else the target must be on the left side then.

package org.wesome.dsalgo;

public class SearchInSortedRotatedArray {
    public static int searchInSortedRotatedArray(int[] arr, int start, int end, int target) {
        if (start > end) {
            return -1;
        }
        int mid = start + (end - start) / 2;
//        If the target element is present in the middle itself
        if (arr[mid] == target) {
            return mid;
        }
//        if the array start is either smaller or equal to mid, then the left part of the array is sorted.
        if (arr[mid] >= arr[start]) {
//        As this sub-array is sorted, we can quickly check if the key lies in half or another half
//            if the key is less than mid because the array is sorted, it means it should be left of the array only
            if (target >= arr[start] && target <= arr[mid]) {
                return searchInSortedRotatedArray(arr, start, mid - 1, target);
            }
//        If the key not lies in the first-half sub-array, Divide another half into two sub-arrays,
//        such that we can quickly check if the key lies in another half
            return searchInSortedRotatedArray(arr, mid + 1, end, target);
        }
//        if the key is greater than mid and less than last then it must be on the right array only.
        if (target >= arr[mid] && target <= arr[end]) {
            return searchInSortedRotatedArray(arr, mid + 1, end, target);
        }
//        else the key must be on the left side then.
        else return searchInSortedRotatedArray(arr, start, mid - 1, target);
    }
}

package org.wesome.dsalgo;

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

import static org.wesome.dsalgo.SearchInSortedRotatedArray.searchInSortedRotatedArray;

public class SearchInSortedRotatedArrayTest {
    @Test
    void binarySearchTest1() {
        int[] arr = new int[]{3, 4, 5, 6, 1, 2};
        int binarySearch = searchInSortedRotatedArray(arr, 0, arr.length - 1, 1);
        Assertions.assertEquals(4, binarySearch);
    }

    @Test
    void binarySearchTest2() {
        int[] arr = new int[]{3, 4, 5, 6, 1, 2};
        int binarySearch = searchInSortedRotatedArray(arr, 0, arr.length - 1, 3);
        Assertions.assertEquals(0, binarySearch);
    }

    @Test
    void binarySearchTest3() {
        int[] arr = new int[]{3, 4, 5, 6, 1, 2};
        int binarySearch = searchInSortedRotatedArray(arr, 0, arr.length - 1, 2);
        Assertions.assertEquals(5, binarySearch);
    }
}

plugins {
    id 'java'
}

group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8

repositories {
    mavenCentral()
}
dependencies {
    testImplementation('org.junit.jupiter:junit-jupiter:5.6.2')
}

test {
    useJUnitPlatform()
}