Search minimum/maximum in a rotated sorted array

• http://www.geeksforgeeks.org/find-minimum-element-in-a-sorted-and-rotated-array/

Solution:

if we take a closer look at above examples, we can easily figure out following pattern: 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

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

Input: {1, 2, 3, 4} Output: 1

Input: {2, 1} Output: 1

Time complexity: O(lgN)

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

private int findMin(int[] array, int low, int high) {
    // This condition is needed to handle the case when array
    // is not rotated at all
    if (high < low) {
        return array[0];
    }

    // If there is only one element left
    if (high == low) {
        return array[low];
    }

    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 && array[mid+1] < array[mid])
        return array[mid+1];

    // Check if mid itself is minimum element
    if (mid > low && array[mid] < array[mid - 1])
        return array[mid];

    // Decide whether we need to go to left half or right half
    if (array[high] > array[mid]) {
        return findMin(array, low, mid - 1);
    } else {
        return findMin(array, mid + 1, high);
    }
}

Follow up: handle duplicate cases:

static 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);
}