Maksim Dmitriev Maksim Dmitriev - 1 month ago 7
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?


Answer

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.