Imagine a perfectly ordered list of numbers, like 1, 2, 3, 4, 5. Now, picture taking a chunk from the beginning and moving it to the end. So, 1, 2, 3, 4, 5 might become 3, 4, 5, 1, 2. The original order is broken, but there's a twist: it's still made of two sorted pieces. Your mission, should you choose to accept it, is to find the absolute smallest number in this rearranged sequence.
At first glance, the simplest approach is to just scan through the entire array, keeping track of the smallest number you've seen. This is straightforward and, honestly, it works. If you're in a hurry or the array is small, this linear scan (O(n) time complexity) will get the job done. In fact, some platforms might even accept this solution without timing out, especially if the test cases aren't designed to push the limits.
But what if you're in an interview, or you just want to be a bit more clever? The fact that the array was sorted, even after rotation, hints at a more efficient method: binary search. This technique, which typically halves the search space with each step, can bring the time complexity down to O(log n).
How does binary search work here? The key is to understand the structure of the rotated array. It's essentially two sorted subarrays. The smallest element will always be the start of the second subarray. We can use comparisons to figure out which half of the array contains this minimum.
A common strategy is to compare the middle element (mid) with the element at the end of the array (end).
- If
nums[mid] > nums[end], it meansmidis in the first, larger part of the rotated array. The minimum element must be somewhere to the right ofmid(in the second, smaller part). So, we discard the left half and update our search range tostart = mid + 1. - If
nums[mid] <= nums[end], it meansmidis either in the second, smaller part of the array, or the array wasn't rotated at all (or rotated by a full cycle, making it appear sorted). In this case, the minimum element could benums[mid]itself, or it could be to its left. So, we discard the right half and update our search range toend = mid.
We continue this process, narrowing down the search space until start and end pointers meet. The element at this final position is our minimum.
There's a subtle point to consider: what if the array contains duplicate numbers? This is where things can get a little trickier. If nums[mid] == nums[end], we can't definitively say whether mid is in the first or second part. For example, in [2, 2, 2, 0, 1], if mid points to the first 2 and end points to 1, nums[mid] > nums[end]. But if mid points to the second 2 and end points to 1, it's still nums[mid] > nums[end]. However, if we have [1, 0, 1, 1, 1], and mid points to the middle 1 and end points to the last 1, nums[mid] == nums[end]. In this scenario, the minimum (0) could be to the left or right of mid. The safest bet when duplicates are involved is to simply decrement end by one (end--). This might degrade the worst-case time complexity to O(n) if the array is filled with identical elements, but it correctly handles all cases.
So, while a simple scan is always an option, understanding the structure of a rotated sorted array unlocks the power of binary search, offering a much more efficient way to pinpoint that elusive minimum value.
