The “Find Minimum in Rotated Sorted Array” problem is a classic question that tests your understanding of binary search and array manipulation. In this blog, we\u2019ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.<\/p>\n\n\n\n
Suppose an array of length Notice that rotating<\/strong> an array Given the sorted rotated array You must write an algorithm that runs in Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n Example 1:<\/strong><\/p>\n\n\n\n Example 2:<\/strong><\/p>\n\n\n\n Example 3:<\/strong><\/p>\n\n\n\n Constraints:<\/strong><\/p>\n\n\n\n Let\u2019s solve the problem in the most straightforward way:<\/p>\n\n\n\n This approach is easy to understand but not efficient for large arrays.<\/p>\n\n\n\nn<\/code> sorted in ascending order is rotated<\/strong> between 1<\/code> and n<\/code> times. For example, the array nums = [0,1,2,4,5,6,7]<\/code> might become:<\/p>\n\n\n\n\n
[4,5,6,7,0,1,2]<\/code>\u00a0if it was rotated\u00a04<\/code>\u00a0times.<\/li>\n\n\n\n[0,1,2,4,5,6,7]<\/code>\u00a0if it was rotated\u00a07<\/code>\u00a0times.<\/li>\n<\/ul>\n\n\n\n[a[0], a[1], a[2], ..., a[n-1]]<\/code> 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]]<\/code>.<\/p>\n\n\n\nnums<\/code> of unique<\/strong> elements, return the minimum element of this array<\/em>.<\/p>\n\n\n\nO(log n) time<\/code>.<\/p>\n\n\n\nInput:<\/strong> nums = [3,4,5,1,2]
Output:<\/strong> 1
Explanation:<\/strong> The original array was [1,2,3,4,5] rotated 3 times.<\/pre>\n\n\n\nInput:<\/strong> nums = [4,5,6,7,0,1,2]
Output:<\/strong> 0
Explanation:<\/strong> The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.<\/pre>\n\n\n\nInput:<\/strong> nums = [11,13,15,17]
Output:<\/strong> 11
Explanation:<\/strong> The original array was [11,13,15,17] and it was rotated 4 times. <\/pre>\n\n\n\n\n
n == nums.length<\/code><\/li>\n\n\n\n1 <= n <= 5000<\/code><\/li>\n\n\n\n-5000 <= nums[i] <= 5000<\/code><\/li>\n\n\n\nnums<\/code>\u00a0are\u00a0unique<\/strong>.<\/li>\n\n\n\nnums<\/code>\u00a0is sorted and rotated between\u00a01<\/code>\u00a0and\u00a0n<\/code>\u00a0times.<\/li>\n<\/ul>\n\n\nBrute Force Solution (Linear Scan)<\/h2>\n\n\n\n
Intuition and Approach<\/h3>\n\n\n\n
\n
Go through the array from start to end.<\/li>\n\n\n\n
Keep updating a variable with the smallest value found so far.<\/li>\n\n\n\n
We check every element, so we\u2019re sure to find the minimum.<\/li>\n<\/ol>\n\n\n\nCode Implementation<\/h3>\n\n\n\n