Eureka Problem
Find Minimum in Rotated Sorted Array
Medium
2 implementations
Categories
Templates
package array.iterative;
public class FindMinimumInRotatedSortedArray {
public int findMin(int[] nums) {
int leftPtr = 0;
int midPtr = -1;
int rightPtr = nums.length - 1;
while (leftPtr <= rightPtr) {
midPtr = leftPtr + (rightPtr - leftPtr) / 2;
if (midPtr > 0 && nums[midPtr - 1] > nums[midPtr])
return nums[midPtr];
if (nums[midPtr] > nums[rightPtr]) leftPtr = midPtr + 1;
else rightPtr = midPtr - 1;
}
return nums[midPtr];
}
}
#include <vector>
class FindMinimumInRotatedSortedArray {
public:
[[nodiscard]] constexpr int findMin(const std::vector<int>& nums) const noexcept {
int left = 0, right = static_cast<int>(nums.size()) - 1;
while (left < right) {
const int mid = left + (right - left) / 2;
if (nums[mid] > nums[right])
left = mid + 1;
else
right = mid;
}
return nums[left];
}
};