Understanding the Problem
We are given a rotated sorted array — an array that was originally sorted in increasing order but has been rotated at some pivot point. Our task is to find the minimum element in this array efficiently.
For example, a sorted array [1, 2, 3, 4, 5]
might become [4, 5, 1, 2, 3]
after rotation. The goal is to identify the smallest number — in this case, 1
— without checking each element one by one.
Step-by-Step Solution with Example
Step 1: Observe if the array is already sorted
If the array is not rotated at all, the first element will be less than the last. In that case, the first element is the smallest. For example, [1, 2, 3, 4, 5]
— here, 1 < 5
, so the minimum is 1
.
Step 2: Initialize Binary Search
We'll use binary search because the array has a sorted structure. Initialize two pointers: low = 0
and high = array.length - 1
.
Step 3: Loop until the search space is narrowed
While low < high
, do the following:
- Calculate
mid = Math.floor((low + high) / 2)
.
- If
array[mid] > array[high]
, it means the minimum is to the right of mid. So, set low = mid + 1
.
- Otherwise, the minimum is at mid or to the left. Set
high = mid
.
Step 4: Return the minimum element
After the loop ends, low == high
, and we have found the index of the minimum element. Return array[low]
.
Step 5: Example Walkthrough
Let’s take [4, 5, 6, 1, 2, 3]
as an example:
- Initial: low = 0, high = 5
- mid = 2 → array[2] = 6, array[5] = 3 → 6 > 3 → minimum must be on the right → low = 3
- mid = 4 → array[4] = 2, array[5] = 3 → 2 ≤ 3 → high = 4
- mid = 3 → array[3] = 1, array[4] = 2 → 1 ≤ 2 → high = 3
- Now low = high = 3 → minimum = array[3] = 1
Edge Cases
- Array not rotated:
[1, 2, 3, 4, 5]
→ min = 1
- Single element:
[7]
→ min = 7
- Two elements:
[10, 5]
→ min = 5
- Empty array: Return
-1
or handle as an invalid input
Finally
This approach is optimal because it uses binary search, which has a time complexity of O(log n)
. By recognizing whether to move left or right based on the middle and end values, we efficiently narrow the search space. This method is both intuitive and scalable for large datasets.
Comments
Loading comments...