Maksim Dmitriev - 1 year ago 63
Java Question

# Find the min in a rotated array. Understanding the implementation

There is a rotated array, and we need to find its min element in log n time. I found several solutions here and can't understand one of them:

``````public int findMin(int[] nums) {
if(nums==null || nums.length==0)
return -1;

int i=0;
int j=nums.length-1;

while(i<=j){
// Sorted (sub)array. We just return its first element.
if(nums[i]<=nums[j])
return nums[i];

int m=(i+j)/2;

if(nums[m]>=nums[i]){
i=m+1; // The pivot is in the right subarray. So we go right
}else{
j=m; // m is the index of the pivot. Why don't we just return it?
}
}

return -1;
}
``````

I see the following three options:

• The (sub)array is sorted. We just return its first element.

• The pivot is in the right subarray. So we go right.

• `m`
is the index of the pivot. So why don't we return it?

In the case you described `nums[m]` is not necessarily the minimum element.
For example, if the array is `[6, 7, 1, 2, 3, 4, 5]`, during the first iteration we've got:
`i = 0`, `j = 6`, `m = 3`. `nums[m] = 2`, which is less than `nums[i]`, but it's clearly not the minimum.