# 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]
}
}