Problem Statement: Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums[] = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

Examples:

Example 1:
Input: nums=[3,4,5,1,2]
Output: 1
Explanation: Original Array was rotated 3 times

Example 2:
Input: nums=[4,5,6,7,0,1,2]
Output:0
Explanation: Original Array was rotated 4 times

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Brute Force Solution

Approach: A basic approach would be to search linearly through the array. Keep a variable minVal=INT_MAX and keep comparing and updating with every element in the array.

Example: [4,5,1,2,3]

Here take, minVal=INT_MAX and start comparing, First, we compare with 4 so minVal is updated to 4. The next 5 get compared, and minVal is unchanged. And so on and at the end minVAl=1. 

Code:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
	int ar[5]={4,5,1,2,3};
	int minVal=INT_MAX,i;
	for(i=0;i<5;i++){
		minVal=min(minVal,ar[i]);
	}
	cout<<"Minimum Value is "<<minVal<<endl;
	return 0;
}

import java.util.*;

class TUF{
public static void main(String args[]){
	int ar[]={4,5,1,2,3};
	int minVal=Integer.MAX_VALUE,i;
	for(i=0;i<5;i++){
		minVal=Math.min(minVal,ar[i]);
	}
	System.out.println("Minimum Value is "+minVal);
   }
}

Optimal Approach

We can optimize the solution using binary search. Since the array is sorted we can see that even after rotation one part of the array will still remain sorted.

For ex : {5,1,2,3,4} here 3,4 is sorted
Ex : [4,5,6,7,0,1,2] left part is sorted from 4 to 7

We take a left pointer, a right pointer, and a mid. So if the left side is sorted, then the leftmost element is the smallest in that part. So we update our minVal and check on the right side. If the right part is sorted then mid is going to be the smallest value for that part, we update the result as min(mid,minVal).

To know which part is sorted, We can observe that while rotation we are bringing the largest element ahead, so if nums[mid]>=nums[left],i.e, if an element greater than it exists further in the array, then that part is sorted. 

if(nums[mid]>=nums[left])

Else we know the right part is sorted. Because at all times at least one side will be sorted.

Another optimization would be if(nums[left]<nums[right])that would mean the whole array between left and right is sorted. We can update the results and break them.

Example:{4,5,1,2,3}
L=0,R=4,Mid=2
Check if arr[mid]> = arr[left], its not, 
So right part is sorted. 
We take res=min(res,arr[mid], res=1, and R = mid-1.

L=0,R=1,Mid=0;
arr[mid]>=arr[left] = true. So we update res as 
min(res,arr[left]), res=1; Since left part was 
sorted L=mid+1. Which makes L=R

L=1,R=1,Mid=1
arr[mid]>=arr[left] = true. So we update res as 
min(res,arr[left]) ,res=1;  Since left part was 
sorted L=mid+1. Which makes L=2. Loop Stops.

Code:

#include<bits/stdc++.h>

using namespace std;
int main() {
  int nums[5] = {4,5,1,2,3};
  int i;
  int left = 0, right = 4, minVal = INT_MAX;

  while (left <= right) {
    if (nums[left] < nums[right]) {
      minVal = min(minVal, nums[left]);
      break;
    }
    int mid = left + (right - left) / 2;

    if (nums[left] <= nums[mid]) {
      minVal = min(minVal, nums[left]);
      left = mid + 1;
    } else {
      minVal = min(minVal, nums[mid]);
      right = mid - 1;
    }
  }
  cout << "Minimum Value is " << minVal;
  return 0;
}

import java.util.*;

class TUF{
public static void main(String args[]) {
  int nums[] = {4,5,1,2,3};
  int i;
  int left = 0, right = 4, minVal = Integer.MAX_VALUE;

  while (left <= right) {
    if (nums[left] < nums[right]) {
      minVal = Math.min(minVal, nums[left]);
      break;
    }
    int mid = left + (right - left) / 2;

    if (nums[left] <= nums[mid]) {
      minVal = Math.min(minVal, nums[left]);
      left = mid + 1;
    } else {
      minVal = Math.min(minVal, nums[mid]);
      right = mid - 1;
    }
  }
  System.out.println("Minimum Value is "+minVal);
}
}

Special thanks to Rishika Gupta for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article