To Find the minimum element in an array which is sorted and Rotated

Question

I recently faced a programming problem which is as follows:

A sorted array is given and the array is rotated at some unknown point, I have to find the minimum element in it. The Array can contain duplicates too.

For eg:

 Input: {5, 6, 1, 2, 3, 4}

 Output: 1  

 Input: {2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 2}   

 Output: 0

I followed simple solution is to traverse trough the complete array and find minimum. This solution requires time O(n).I understand the fact that the minimum element is the one whose previous element is greater than it. If there is no such element present, then there is no rotation and first element would be the minimum.

But i was asked for a O(Logn) solution. Is there a way to solve it in in O(Logn) time?

Answer 1

Find minimum element in a sorted and rotated array in Java

package yourPackageNameGoesHere;

public class yourClassNameGoesHere {

public static void main(String[] args) {
      int arr[]={16,19,21,25,3,5,8,10};
      findMinimumElementInSortedAndRotatedArray(arr);
}

public static void findMinimumElementInSortedAndRotatedArray(int[] arr) {
    int mid = arr.length / 2;
    boolean pivotFound = false;
    int pivotIndex = -1;

    for (int rightSide = mid; rightSide < arr.length - 1; rightSide++) {
        if (arr[rightSide] > arr[rightSide + 1]) {
            pivotIndex = rightSide;
            pivotFound = true;
            System.out.println("1st For Loop. Pivot is: " + arr[pivotIndex] + ". Pivot Index is: " + pivotIndex);
            break;
        }
    }
    if (!pivotFound) {
        for (int leftSide = 0; leftSide < mid; leftSide++) {
            if (arr[leftSide] > arr[leftSide + 1]) {
                pivotIndex = leftSide;
                System.out.println("1st For Loop. Pivot is: " + arr[pivotIndex] + ". Pivot Index is: " + pivotIndex);
                break;
            }
        }
    }
    String textForSmall = "Smallest Number is ";
    if (pivotIndex != arr.length - 1 && pivotIndex != 0) {
        System.out.println(arr[0] < arr[pivotIndex + 1] ? textForSmall + arr[0] : textForSmall + arr[pivotIndex + 1]);
    } else {
        System.out.println(arr[0] < arr[pivotIndex] ? textForSmall + arr[0] : textForSmall + arr[pivotIndex]);
    }
}

}

Answer 2

public class MinElementInRotatedArrayUsingRecursion {

    public static void main(String[] args) {
        int arr1[] = { 5, 6, 1, 2, 3, 4 };
        int n1 = arr1.length;
        System.out.println("The minimum element is " + findMin(arr1));

        int arr2[] = { 1, 2, 3, 4 };
        int n2 = arr2.length;
        System.out.println("The minimum element is " + findMin(arr2));

        int arr3[] = { 1 };
        int n3 = arr3.length;
        System.out.println("The minimum element is " + findMin(arr3));

        int arr4[] = { 1, 2 };
        int n4 = arr4.length;
        System.out.println("The minimum element is " + findMin(arr4));

        int arr5[] = { 2, 1 };
        int n5 = arr5.length;
        System.out.println("The minimum element is " + findMin(arr5));

        int arr6[] = { 5, 6, 7, 1, 2, 3, 4 };
        int n6 = arr6.length;
        System.out.println("The minimum element is " + findMin(arr6));

        int arr7[] = { 1, 2, 3, 4, 5, 6, 7 };
        int n7 = arr7.length;
        System.out.println("The minimum element is " + findMin(arr7));

        int arr8[] = { 2, 3, 4, 5, 6, 7, 8, 1 };
        int n8 = arr8.length;
        System.out.println("The minimum element is " + findMin(arr8));

        int arr9[] = { 3, 4, 5, 1, 2 };
        int n9 = arr9.length;
        System.out.println("The minimum element is " + findMin(arr9));

    }// main

    public static int findMin(int[] num) {
        return findMin(num, 0, num.length - 1);
    }

    public static int findMin(int[] num, int start, int last) {
        // only 1 element
        if (start == last)
            return num[start];
        // only 2 elements
        if ((last - start) == 1)
            return Math.min(num[start], num[last]);

        int middle = start + (last - start) / 2;

        // not rotated
        if (num[start] < num[last]) {
            return num[start];
        }

        // go last side
        /*
         * int[] a = 2,3,4,5,1
         *  a[start]=2 and a[last]=1 and a[mid] = 4 
         *  a[mid] > a[start]
         * Then, as the array is rotated, That's why, calculation will start from
         * a[middle] to a[last]
         */
        else if (num[middle] > num[start]) {
            return findMin(num, middle, last);
        } else {

            // go start side
            /*
             * int[] a = 4,5,1,2,3 
             * a[start]= 4 and a[last]=3 and a[mid] = 1 
             * a[mid] < a[start]
             * Then, as the array is rotated, That's why, calculation will start from
             * a[start] to a[middle]
             */
            return findMin(num, start, middle);
        }
    }
}

The iterative method:

public class MinElementInRotatedArrayUsingRecursionAndIteration {

    public static void main(String[] args) {
        int arr1[] = { 5, 6, 1, 2, 3, 4 };
        int n1 = arr1.length;
        System.out.println("The minimum element is " + findMin(arr1));

        int arr2[] = { 1, 2, 3, 4 };
        int n2 = arr2.length;
        System.out.println("The minimum element is " + findMin(arr2));

        int arr3[] = { 1 };
        int n3 = arr3.length;
        System.out.println("The minimum element is " + findMin(arr3));

        int arr4[] = { 1, 2 };
        int n4 = arr4.length;
        System.out.println("The minimum element is " + findMin(arr4));

        int arr5[] = { 2, 1 };
        int n5 = arr5.length;
        System.out.println("The minimum element is " + findMin(arr5));

        int arr6[] = { 5, 6, 7, 1, 2, 3, 4 };
        int n6 = arr6.length;
        System.out.println("The minimum element is " + findMin(arr6));

        int arr7[] = { 1, 2, 3, 4, 5, 6, 7 };
        int n7 = arr7.length;
        System.out.println("The minimum element is " + findMin(arr7));

        int arr8[] = { 2, 3, 4, 5, 6, 7, 8, 1 };
        int n8 = arr8.length;
        System.out.println("The minimum element is " + findMin(arr8));

        int arr9[] = { 3, 4, 5, 1, 2 };
        int n9 = arr9.length;
        System.out.println("The minimum element is " + findMin(arr9));

    }// main

    // iterative method
    public static int findMin(int[] nums) {


        int start =0; 
        int last =nums.length-1;

        while(start <= last){
            if(nums[start]<=nums[last]) return nums[start];

            int mid =(start + last)/2;
            /*  int[] a =  2,3,4,5,1
             a[start]=2 and a[last]=1
             a[mid] = 4
             a[mid] > a[start] 
            Then, as the array is rotated, That's why, calculation will start from a[middle] to a[last]
    */
            if(nums[mid]>=nums[start]){
                start = mid +1;
            }else{
                /*  int[] a =  4,5,1,2,3
             a[start]= 4 and a[last]=3
             a[mid] = 1
             a[mid] < a[start] 
            Then, as the array is rotated, That's why, calculation will start from a[start] to a[middle]
       */
                last = mid;
            }
        }

        return -1;
    }

}

Answer 3

see this : Since it is sorted array. i need to apply binary search to find pivot..

Lowest element will be where array was pivoted.

Call this findpivot(arr,0,n-1);

int findPivot(int arr[], int low, int high)
{
   // base cases
   if (high < low)  return -1;
   if (high == low) return low;

   int mid = (low + high)/2;   /*low + (high - low)/2;*/
   if (mid < high && arr[mid] > arr[mid + 1])
     return mid;
   if (mid > low && arr[mid] < arr[mid - 1])
     return (mid-1);
   if (arr[low] >= arr[mid])
     return findPivot(arr, low, mid-1);
   else
     return findPivot(arr, mid + 1, high);
}

Answer 4

Off the top of my head:

• Note the first entry
• Perform a binary search; at each stage choose the right half if the pivot element is greater than or equal to the stored first element, and the left half if the pivot element is less.

For instance, given {4,5,6,7,1,2,3}:

• Pivot at 7 > 4, reduce to right half {1,2,3}
• Pivot at 2 < 4, reduce to left half 1.
• Considering only one element, answer is 1.