Find min sublist in unsorted array so that if it is sorted then the whole list is sorted

This post is responding to Li Peng's post: http://allenlipeng47.com/PersonalPage/index/view/102/nkey

Start from left, increase pointer until the element is no longer ascending, then do binary search, find the left boundary, continue move the pointers until meeting another element which is smaller, then do binary search to update the left boundary. Do the same for right boundary. 


The key to this solution is do the binary search correctly, watching out the boundary case. Since we are not looking for number but the closest number in the list, so we need to 1) exit the while() loop when there are only two elements left in the search window, 2) include the middle number in the search window.

static int[] findMinUnsortedWindow2(int[] nums){
 int p=0, len = nums.length, left = Integer.MAX_VALUE, right = Integer.MIN_VALUE;
 while(p<len){
while(p+1<len && nums[p+1]>=nums[p]){p++;}

if(p+1<len)//we found the number broke the order, do binary search

  left = Math.min(left, binarySearch3(nums, 0, Math.min(p,  left), nums[p+1]));
p++;
}

//use -1, -1 to indicate the array is sorted already

if(left == Integer.MAX_VALUE)
return new int[]{-1, -1};

p=len-1;
while(p>=0){
while(p-1>=0 && nums[p-1]<=nums[p]){p--;}
if(p-1>=0)
  right = Math.max(right, binarySearch4(nums, Math.max(p, right), len-1, nums[p-1]));
p--;
}

return new int[]{left, right};

}

//find the minimum index i which nums[i] bigger than k in sorted array

static int binarySearch3(int[] nums, int p0, int p1, int k){
while(p0<p1-1){//binary search window size is larger than 2 elements
int mid = (p0+p1)/2;
if(nums[mid]>k)
p1 = mid;//including the middle in search window

else

p0 = mid;
}
return nums[p0]>k?p0:p1;
}

//find the maximum index i which nums[i] smaller than k in sorted array

static int binarySearch4(int[] nums, int p0, int p1, int k){
while(p0<p1-1){
int mid = (p0+p1)/2;
if(nums[mid]<k)
p0 = mid;
else
p1 = mid;
}
return nums[p1]<k?p1:p0;
}