The C language outputs the algorithm principle and the example of the minimum number elements in the rotated array

  • 2020-05-09 19:00:41
  • OfStack

  problem description: moving the first elements of an array to the end of the array is called array rotation. Input 1 rotation of a sorted array and output the smallest element of the rotated array. For example, the array {3, 4, 5, 1, 2} is one rotation of {1, 2, 3, 4, 5}, and the minimum value of the array is 1.
The most intuitive way to solve this problem is not difficult. You can find the smallest element by going through the groups once, and the time complexity is obviously O(n). But this idea doesn't take advantage of the nature of input arrays. Since there is an algorithm with less time complexity, it is easy to think of a two-point lookup, because its time complexity is O(logn). Can this problem be looked up using 2 points? The answer is yes. Look at the array properties of 1, first incrementing (called incrementing a), then suddenly dropping to the minimum, and then incrementing again (called incrementing b). Of course, there is also a special case where the array is increasing without decreasing, that is, the number of rotating elements is 0.
        for the 1-like case, suppose A is the input array, left and right are the left and right boundary coordinates of the array, investigate the middle position of the value A[mid], if A[mid] < = A[right], indicating an increasing b, adjust the right boundary right = mid; If A [mid] > = A[left], indicating an increasing a, so adjust the left edge left = mid. When the left and right edges are adjacent, the smaller one is the minimum value of the array. In fact, in the general case of 1, the element referred to by the right boundary is the minimum value.
        for special cases, the number of rotations is 0. According to the algorithm above, the right boundary will decrease until it is adjacent to the left boundary. In this case, the element referred to by the left boundary is the minimum value. Here are some test cases:

//{1,2,3,4,5,6,7,8,9,10}  1 
//{4,5,6,7,8,9,10,1,2,3}  1 
//{1,1,1,1,1,1,1,1,1,1}  1 
//{1,9,10,1,1,1,1,1,1,1}  1 
//{9,9,9,9,9,9,9,10,1,9}  9  error  

The results of group 5 of         were wrong. In fact, the above algorithm is suitable for strictly increasing array, for the non-strictly increasing array, the two-point method cannot guarantee the correct solution. For those of you who are interested, you can see if you can get the right solution using the two-point method for sequences that are not strictly increasing.
        reference code:

// The functionality   :   Rotates the smallest element of the array   
// Function parameters   :  pArray Pointing to an array, len Is the array length  
// The return value   :    The smallest element  
int FindMin(int *pArray, int len) 
  if(pArray == NULL || len <= 0) 
    return 0; 
  int left = 0, right = len - 1, mid; 
  while(right - left != 1) 
     mid = left + ((right - left)>>1); 
     if(pArray[right] >= pArray[mid])  
       right = mid; 
     else if(pArray[left] <= pArray[mid])     
       left = mid; 
  return pArray[right] > pArray[left] ? pArray[left]: pArray[right]; 

Related articles: