# Solution For Find Minimum In Rotated Sorted Array

The problem “Find Minimum in Rotated Sorted Array” on LeetCode can be solved efficiently using the Binary Search algorithm. The problem statement is as follows:

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element in the array.

You may assume no duplicate exists in the array.

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

Example 2:
Input: [4,5,6,7,0,1,2] Output: 0

To solve this problem, we can make use of Binary Search algorithm by finding the pivot element. The pivot element is the minimum element in the array and it is the element that is the result of rotation of the original sorted array.

The approach to solve this problem is as follows:

1. Initialize left and right pointers to the start and end of the array respectively.
2. While the left pointer is less than the right pointer, compute the mid value as (left + right) / 2.
3. If the mid value is greater than the element at the right pointer, then shift the left pointer i.e., left = mid + 1.
4. Otherwise, shift the right pointer i.e., right = mid.
5. Once the while loop terminates, the minimum element will be at the left pointer.

The implemented code in Python is as follows:

class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) – 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]

## Step by Step Implementation For Find Minimum In Rotated Sorted Array

```class Solution {
public int findMin(int[] nums) {

// check for empty or null array
if (nums == null || nums.length == 0) {
return -1;
}

// initialize left and right pointers
int left = 0;
int right = nums.length - 1;

// if the array is not rotated, the minimum element will be the first element
if (nums[left] < nums[right]) {
return nums[left];
}

// binary search for the minimum element
while (left <= right) {
// find the midpoint
int mid = left + (right - left) / 2;

// if the midpoint is the minimum element, return it
if (nums[mid] > nums[mid + 1]) {
return nums[mid + 1];
}
// if the midpoint is greater than the first element, that means the minimum element is still to the right
else if (nums[mid] > nums[left]) {
left = mid + 1;
}
// if the midpoint is less than the first element, that means the minimum element is to the left
else {
right = mid;
}
}

return -1;
}
}```
```# Solution 1:

class Solution:
def findMin(self, nums: List[int]) -> int:
# Base case
if len(nums) == 1:
return nums[0]

# General case
left = 0
right = len(nums) - 1

# Check if the array is already sorted
if nums[right] > nums[left]:
return nums[left]

# Perform binary search
while left <= right:
# Find the middle element
mid = left + (right - left) // 2

# Check if the middle element is the minimum element
if nums[mid] > nums[mid + 1]:
return nums[mid + 1]

# Check if the middle element is greater than the first element
# This means the minimum element is still to the right of the middle element
if nums[mid] >= nums[left]:
left = mid + 1

# Otherwise, the minimum element is to the left of the middle element
else:
right = mid```
```/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function(nums) {

};```
```class Solution {
public:
int findMin(vector& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}
};```
`public int FindMin(int[] nums) { // check for empty or null array if (nums == null || nums.Length == 0) { return -1; } // set left and right indices int left = 0; int right = nums.Length - 1; // loop until left index passes right index while (left <= right) { // calculate middle index int middle = left + (right - left) / 2; // if middle element is greater than element to its right, // the minimum must be to the right of the middle element if (nums[middle] > nums[middle + 1]) { return nums[middle + 1]; } // if middle element is less than element to its left, // the minimum must be to the left of the middle element if (nums[middle] < nums[middle - 1]) { return nums[middle]; } // if neither of the above is true, // the array is not rotated and the minimum is the first element if (nums[left] <= nums[middle]) { // if the first element is less than or equal to the middle element, // the minimum cannot be to the left of the first element, so move the left index to the right left = middle + 1; } else { // if the first element is greater than the middle element, // the minimum cannot be to the right of the middle element, so move the right index to the left right = middle - 1; } } // if the left index passes the right index, the minimum is the first element return nums[0]; }`
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]