Interview question 16.16 Partial sorting - Double finger needling

Interview questions 16.16. Partial sorting

Given an array of integers , Write a function , Find the index m and n, Just index the range [m,n] The elements of are in order , The whole array is ordered . Be careful ：n-m As little as possible , in other words , Find the shortest sequence that meets the conditions . The return value of the function is [m,n], If there is no such m and n（ For example, the whole array is ordered ）, Please return [-1,-1].

Example ：

Input ： [1,2,4,7,10,11,7,12,6,7,16,18,19]
Output ： [3,9]

The solution code is as follows ：

/** * Note: The returned array must be malloced, assume caller calls free(). */
int* subSort(int* array, int arraySize, int* returnSize){
    
    int low=0,high=arraySize-1;
      int *re=(int *)malloc(sizeof(int)*2);
    re[0]=-1;
    re[1]=-1;
     *returnSize=2;
 if(arraySize<=1){
    
      
    
     return re;
    }
    while(array[low]<=array[low+1]){
    
        low++;
      // printf("%d ",low);
        if(low==arraySize-1){
    
         
            return re;

        }
    }
    while(array[high-1]<=array[high]){
    
        high--;
        if(high==0){
    
             return re;
        }
    }
     // printf("low high %d %d",low,high);
    int i;
    int min=999,max=-1000;
    for(i=low;i<=high;i++){
    
        if(array[i]<min){
    
            min=array[i];
        }
        if(array[i]>max){
    
            max=array[i];
        }
     
    }
   // printf("min max %d %d",min,max);
    
    while(array[low]>min){
    
       
           if(low==0){
    
         
           break;

        }
         low--;
           if(low==0){
    
         
           break;

        }
    }

     while(array[high]<max){
    
      
         if(high==arraySize){
    
         
           break;

        }
          high++;
          if(high==arraySize){
    
         
           break;

        }
    }
    
     if(low==0){
    
         low--;

     }
    re[0]=low+1;
    re[1]=high-1;
     *returnSize=2;
     return re;

    
}