Find Rotation Count In Sorted Rotated Array

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 and Pivot element is the point from where rotation started. for example

The Algorithm is simple, The Pivot of arrays is the index from where rotation started. so find the Pivot index.

1. Find mid of the array
2. If the mid is greater than its next, then mid is the pivot
3. If the mid is less than its previous, then the previous is the pivot
4. If mid is less than the start, then the pivot must be on the left subarray of mid
5. If mid is greater than the start, then the pivot must be on the right subarray of mid
6. if none of the above cases matches it means the array is not rotated

package org.wesome.dsalgo;

public class RotationCountInSortedRotatedArray {
    public static int rotationCountInSortedRotatedArray(int[] arr) {
        int pivot = pivotInSortedRotatedArray(arr);
        return pivot + 1;
    }

    public static int pivotInSortedRotatedArray(int[] arr) {
        int start = 0;
        int end = arr.length - 1;
        while (start <= end) {

            int mid = start + (end - start) / 2;

//  if mid-element is greater than its next, then mid is the pivot
            if (mid < end && arr[mid] > arr[mid + 1]) {
                return mid;
            }
//            if the middle element is less than its previous element, then the previous element is the pivot
            if (mid > start && arr[mid] < arr[mid - 1]) {
                return mid - 1;
            }
// if mid is less than the start element, then the pivot must be on the left sub-array of mid
            if (arr[mid] <= arr[start]) {
                end = mid - 1;
            }
//            mid is greater than the start element, then the pivot must be on the right subarray of mid
            else {
                start = mid + 1;
            }
        }
//        array is not rotated
        return -1;
    }
}

package org.wesome.dsalgo;

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

import static org.wesome.dsalgo.RotationCountInSortedRotatedArray.rotationCountInSortedRotatedArray;

public class RotationCountInSortedRotatedArrayTest {
    @Test
    void rotationCountInSortedRotatedArrayTest1() {
        int[] arr = new int[]{3, 4, 5, 6, 1, 2};
        int rotationCountInSortedRotatedArray = rotationCountInSortedRotatedArray(arr);
        Assertions.assertEquals(4, rotationCountInSortedRotatedArray);
    }

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

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

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