Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/153.html
Suppose a sorted array 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).
Find the minimum element.
You may assume no duplicate exists in the array.
@tag-array
Algorithm
Compare the middle value nums[mid] with the right boundary value nums[right]. If the array is not rotated or the rotation point is in the left half, the middle value must be less than the right boundary value, so go to the left half to continue searching , Otherwise, go to the right half to search, and finally return nums[right].
Code
-
public class Find_Minimum_in_Rotated_Sorted_Array { public class Solution_iteration { public int findMin(int[] nums) { if (nums == null || nums.length == 0) { return 0; } // min is possibly found in 3 cases (eg. 1,2,3,4,5): // 1. min at left half (eg. 5,1,2,3,4) // 2. min at right half (eg. 2,3,4,5,1) // 3. min at mid position (eg. 4,5,1,2,3) // 2 cases: // 1,2,3,4,5 // @note:@memorize: but this case is included in above if check // 2,3,4,5,1 int low = 0; // left pointer int high = nums.length - 1; // right pointer /* @note: to restore thinking process while (low <= high) { int mid = low + (high - low) / 2; if (nums[low] < nums[high]) { // meaning not rotated return nums[low]; } else if (nums[mid] > nums[low]) { // left part sorted low = mid; } else { // (nums[mid] <= nums[i]) { // right part sorted @note: '=' is crucial // j = mid - 1; high = mid; } } */ while (low < high && nums[low] > nums[high]) { // @note: if low < high, then un-rotated, return low int mid = low + (high - low) / 2; if (nums[mid] > nums[high]) { low = mid + 1; } else { high = mid; // @note: here, not "high=mid-1" } /* * @note: below not working, for input [2,1], infinite loop why? because, if mid>high, then mid is never min, so mid+1 if mid<=high, then mid could be max in this case, if change the question to be, "find max in rotated sorted array"? then, the mid check is the opposite if (nums[mid] > nums[high]) { low = mid; } else { high = mid - 1; } */ } return nums[low]; } } } ############ class Solution { public int findMin(int[] nums) { int n = nums.length; if (nums[0] <= nums[n - 1]) { return nums[0]; } int left = 0, right = n - 1; while (left < right) { int mid = (left + right) >> 1; if (nums[0] <= nums[mid]) { left = mid + 1; } else { right = mid; } } return nums[left]; } }
-
// OJ: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array // Time: O(logN) // Space: O(1) class Solution { public: int findMin(vector<int>& A) { int L = 0, R = A.size() - 1; while (L < R) { int M = (L + R) / 2; if (A[M] > A[R]) L = M + 1; else R = M; } return A[L]; } };
-
class Solution: def findMin(self, nums: List[int]) -> int: if nums[0] <= nums[-1]: return nums[0] left, right = 0, len(nums) - 1 while left < right: mid = (left + right) >> 1 if nums[0] <= nums[mid]: left = mid + 1 else: right = mid return nums[left] ############ class Solution(object): def findMin(self, nums): """ :type nums: List[int] :rtype: int """ start, end, mid = 0, len(nums) - 1, 0 while start + 1 < end: mid = start + (end - start) / 2 if nums[start] <= nums[mid]: start = mid else: end = mid return min(nums[0], nums[start], nums[end])
-
func findMin(nums []int) int { n := len(nums) if nums[0] <= nums[n-1] { return nums[0] } left, right := 0, n-1 for left < right { mid := (left + right) >> 1 if nums[0] <= nums[mid] { left = mid + 1 } else { right = mid } } return nums[left] }
-
function findMin(nums: number[]): number { let left = 0; let right = nums.length - 1; while (left < right) { const mid = (left + right) >>> 1; if (nums[mid] > nums[right]) { left = mid + 1; } else { right = mid; } } return nums[left]; }
-
/** * @param {number[]} nums * @return {number} */ var findMin = function (nums) { const n = nums.length; if (nums[0] <= nums[n - 1]) { return nums[0]; } let left = 0, right = n - 1; while (left < right) { const mid = (left + right) >> 1; if (nums[0] <= nums[mid]) { left = mid + 1; } else { right = mid; } } return nums[left]; };
-
impl Solution { pub fn find_min(nums: Vec<i32>) -> i32 { let mut left = 0; let mut right = nums.len() - 1; while left < right { let mid = left + (right - left) / 2; if nums[mid] > nums[right] { left = mid + 1; } else { right = mid; } } nums[left] } }