Find Minimum in Rotated Sorted Array

The "Find Minimum in Rotated Sorted Array" problem is an intriguing search problem that involves finding the minimum element in a sorted array that has been rotated at some unknown pivot point.

Problem Statement

Given a rotated sorted array, the goal is to find the minimum element. The original array is sorted in ascending order but then rotated at some pivot.

Examples

1. Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times.

2. Input: nums = [4,5,6,7,0,1,2] Output: 0 Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Constraints

• 1 <= nums.length <= 5000
• -5000 <= nums[i] <= 5000
• The array is sorted and rotated at some pivot.

Binary Search Solution

The solution leverages a modified binary search due to the sorted nature of the array:

Explanation

• The algorithm initiates a binary search. However, instead of searching for a specific value, it looks for the inflection point.
• The inflection point is where we find the smallest element.
• The logic in the binary search is modified to find this point by comparing the middle element with the rightmost element to decide which half of the array to continue the search.

This problem is a classic example used in interviews to assess a candidate's proficiency in modifying and applying binary search in different scenarios.

Rust Solution

Vec<i32> is taken by value, so find_min owns the vector and indexes it directly with nums[mid] and nums[right] without any borrow. The let mut left and let mut right bindings need the explicit mut because Rust bindings are immutable by default, and both are inferred as unsigned indices from nums.len() - 1. The bare nums[left] on the last line is the return value: Rust treats the final expression, with no return keyword and no trailing semicolon, as the function's result. The vec! macro builds the test inputs in main.

Go Solution

left, right := 0, len(nums)-1 uses Go's := short declaration to bind both indices in a single statement, with the len(nums) builtin sizing the slice. Go has no while, so the loop is a bare for left < right. The parameter is a []int slice, indexed directly as nums[mid] and nums[right], and the answer comes back through an explicit return nums[left] rather than a trailing expression as in the Rust version.