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

Original array       1, 2, 3, 4, 5       Pivot is -1
Rotation Count 1    5, 1, 2, 3, 4   Pivot is 5
Rotation Count 2    4, 5, 1, 2, 3   Pivot is 5
Rotation Count 3    3, 4, 5, 1, 2   Pivot is 5
Rotation Count 4    2, 3, 4, 5, 1   Pivot is 5
Rotation Count 5    1, 2, 3, 4, 5   Pivot is -1

The Algorithm is simple

  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 PivotInSortedRotatedArray {
    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.PivotInSortedRotatedArray.pivotInSortedRotatedArray;

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

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

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