Given a sorted array which is rotated at some unknown point, find the minimum element in that array

### Example

**INPUT :**

arr[] = {5,6,7,1,2,3,4}

**OUTPUT :**

The minimum element is 1

In the above example, the input is the rotated sorted array ie, sorted array will be {1,2,3,4,5,6,7} and the rotated sorted array is {5,6,7,1,2,3,4}. The output 1 is the minimum element in that array.

**Time Complexity: O(logn)**

The main idea is, the element is said to be minimum in rotated sorted array if the previous element to it is greater than it or there is no previous element(ie, no rotation)

We can do this using Binary search

## Algorithm

**1.** Find the mid element ie, mid = (low+high)/2

**2.** If the (mid+1)th element is less than mid element then return (mid+1)th element

**3.** If the mid element is less than (mid-1)th element then return the mis element

**4.** If the last element is greater than mid element then search in left half

**5.** If the last element is less than mid element then search in right half

## C++ Program

#include <bits/stdc++.h> using namespace std; int findMinimum(int arr[],int low, int high) { int mid = (low + high)/2; //when array is not rotated at all if (arr[high] > arr[low]) { return arr[0]; } //if there is only one element if (high == low) { return arr[low]; } //if the element (mid + 1) is the minimum if (mid< high && arr[mid+1] <arr[mid]) { return arr[mid+1]; } //If the mid element is the minimum if (mid > low && arr[mid] <arr[mid-1]) { return arr[mid]; } //search in the left half if (arr[high]>arr[mid]) { return findMinimum(arr, low, mid-1); } //search in the right half else { return findMinimum(arr,mid+1,high); } } int main() { int arr[]= {5,6,7,1,2,3,4}; //creating an array int n = sizeof(arr)/sizeof(arr[0]); //size of the array cout<<"The minimum element is "<<findMinimum(arr,0,n-1); return 0; }

## Given a sorted array which is rotated at some unknown point, find the minimum element in that array

### Example

**INPUT :**

arr[] = {5,6,7,1,2,3,4}

**OUTPUT :**

The minimum element is 1

In the above example, the input is the rotated sorted array ie, sorted array will be {1,2,3,4,5,6,7} and the rotated sorted array is {5,6,7,1,2,3,4}. The output 1 is the minimum element in that array.

**Time Complexity: O(logn)**

The main idea is, the element is said to be minimum in rotated sorted array if the previous element to it is greater than it or there is no previous element(ie, no rotation)

We can do this using Binary search

## Algorithm

**1.** Find the mid element ie, mid = (low+high)/2

**2.** If the (mid+1)th element is less than mid element then return (mid+1)th element

**3.** If the mid element is less than (mid-1)th element then return the mis element

**4.** If the last element is greater than mid element then search in left half

**5.** If the last element is less than mid element then search in right half

## C++ Program

#include <bits/stdc++.h> using namespace std; int findMinimum(int arr[],int low, int high) { int mid = (low + high)/2; //when array is not rotated at all if (arr[high] > arr[low]) { return arr[0]; } //if there is only one element if (high == low) { return arr[low]; } //if the element (mid + 1) is the minimum if (mid< high && arr[mid+1] <arr[mid]) { return arr[mid+1]; } //If the mid element is the minimum if (mid > low && arr[mid] <arr[mid-1]) { return arr[mid]; } //search in the left half if (arr[high]>arr[mid]) { return findMinimum(arr, low, mid-1); } //search in the right half else { return findMinimum(arr,mid+1,high); } } int main() { int arr[]= {5,6,7,1,2,3,4}; //creating an array int n = sizeof(arr)/sizeof(arr[0]); //size of the array cout<<"The minimum element is "<<findMinimum(arr,0,n-1); return 0; }