Maksim Dmitriev - 7 months ago 31

Java Question

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.
- is the index of the pivot. So why don't we return it?
`m`

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.

Source (Stackoverflow)