Find the minimum element in a sorted and rotated array | GeeksforGeeks

A sorted array is rotated at some unknown point, find the minimum element in it.

The minimum element is the only element whose previous element is greater than it. If there is no such element, then there is no rotation and first element is the minimum element. Therefore, we do binary search for an element which is smaller than the previous element.

int findMin(int arr[], int low, int high)

{

    // This condition is needed to handle the case when array is not

    // rotated at all

    if (high < low)  return arr[0];

    // If there is only one element left

    if (high == low) return arr[low];

    // Find mid

    int mid = low + (high - low)/2; /*(low + high)/2;*/

    // Check if element (mid+1) is minimum element. Consider

    // the cases like {3, 4, 5, 1, 2}

    if (mid < high && arr[mid+1] < arr[mid])

       return arr[mid+1];

    // Check if mid itself is minimum element

    if (mid > low && arr[mid] < arr[mid - 1])

       return arr[mid];

    // Decide whether we need to go to left half or right half

    if (arr[high] > arr[mid])

       return findMin(arr, low, mid-1);

    return findMin(arr, mid+1, high);

}

How to handle duplicates?
It turned out that duplicates can’t be handled in O(Logn) time in all cases. It doesn’t look possible to go to left half or right half by doing constant number of comparisons at the middle. Following is an implementation that handles duplicates. It may become O(n) in worst case though.

int findMin(int arr[], int low, int high)

{

    // This condition is needed to handle the case when array is not

    // rotated at all

    if (high < low)  return arr[0];

    // If there is only one element left

    if (high == low) return arr[low];

    // Find mid

    int mid = low + (high - low)/2; /*(low + high)/2;*/

    // Check if element (mid+1) is minimum element. Consider

    // the cases like {1, 1, 0, 1}

    if (mid < high && arr[mid+1] < arr[mid])

       return arr[mid+1];

    // This case causes O(n) time

    if (arr[low] == arr[mid] && arr[high] == arr[mid])

        return min(findMin(arr, low, mid-1), findMin(arr, mid+1, high));

    // Check if mid itself is minimum element

    if (mid > low && arr[mid] < arr[mid - 1])

       return arr[mid];

    // Decide whether we need to go to left half or right half

    if (arr[high] > arr[mid])

       return findMin(arr, low, mid-1);

    return findMin(arr, mid+1, high);

}

Read full article from Find the minimum element in a sorted and rotated array | GeeksforGeeks