C program to find the minimum element in a sorted and rotated array

In this blog post, we learn how to write a C program to find the minimum element in a sorted and rotated array? So here we will write a C program to find the minimum element in a sorted and rotated array.

Suppose an array ( ‘arr’ ) sorted in ascending order is rotated at some pivot unknown to you beforehand.(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2 ).

Now here task to search the minimum element in a sorted and rotated array.

Note: Input array must be sorted.

If you want to learn more about the C language, you can check this course, Free Trial Available.

Get Your Free Trial 
#include <stdio.h>
#include <stdint.h>

//Calculate array size
#define ARRAY_SIZE(arr)  sizeof(arr)/sizeof(arr[0])


int minInRotatedArray(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 minInRotatedArray(arr, low, mid-1);
    return minInRotatedArray(arr, mid+1, high);
}


//print array elements
void printArray(int arr[], int n)
{
    int i;
    for (i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
}


int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6};

    //get array size
    const int arr_size = ARRAY_SIZE(arr);

    const int minElement = minInRotatedArray(arr,0,arr_size-1);

    printf("Min in Sorted Rotated Array = %d\n",minElement);

    return 0;
}
minimum element in a sorted and rotated array

Recommended Articles for you: