Given a sorted array that has been already rotated, we need to find the minimum element.
Example:
{4,6,7,2,3,4} Ans: 2
Solution:
To solve this, we need to find the element in the array where we see the rotation started/ended. We can call this element the pivot element where the subarrays before and after it are sorted.
In the above example, we can see that 2 is the pivot since we have two sub arrays that are sorted before and after it. A1 = {4,6,7} A2= {2,3,4}
We can easily solve this problem by finding the pivot element, in this case 2.
We can find it by checking if there is increase by 1 to the array's next element.
In the case where there is no rotation and hence no pivot, we simply return the first element.
public int FindMin(int[] nums) {
for (int i = 0; i < nums.Length - 1; i++) {
if (nums[i] > nums[i + 1])
return nums[i + 1];
}
return nums[0];
}