【算法】找出数组置尾操作的次数

0x55AA

题目：
一个递增的整形数组，现在的操作是每次从数组的开头取出一个元素放在数组的末尾，连续n次这样的操作后得到一个新的数组，现在把这个数组给你，请求出最少移动的次数。
解析：
1 最容易想到的方法就是依次遍历这个数组，找到最小值的位置，这样的时间复杂度就是O(n)。
2 考虑到事先是排好序的，所以我们可以使用二分查找法来实现这个操作，只不过是这个二分查找法是传统二分查找法的变种。
这里我们只要考虑以下3种情况。
<1>数组先递增再递减，中值大于左值，那么此时的最小值就处于数组的右半部。
<2>数组先递增再递减，中值小于左值，那么此时的最小值就处于数组的左半部。
<3>数组单调递增，此时的最小值就是数组的首元素。

3 程序实现
根据解析中2的思想，采取二分查找法的程序如下所示：

1. #include <iostream>
   
2. using namespace std;
   
3. int getInvertNumber(int arr[],int nLength);
   
4. 
   
5. void main()
   
6. {
   
7.         int arr[] = {1,2,3,4,5,6,7,8,9};
   
8.         int brr[] = {1,3,4,6,8,9};
   
9.         int sb = getInvertNumber(brr,sizeof(brr)/sizeof(brr[0]));
   
10.         cout<<sb<<endl;
    
11. 
    
12. }
    
13. 
    
14. int getInvertNumber(int arr[],int nLength)
    
15. {
    
16.         int nLeft = 0;
    
17.         int nRight = nLength-1;
    
18.         int nMid;
    
19.         if(arr[nLeft]<arr[nRight])
    
20.                 return 0;
    
21.         while(nLeft<nRight)
    
22.         {
    
23.                 nMid = ( nLeft + nRight ) / 2;
    
24.                 if(arr[nMid]>arr[nLeft])
    
25.                         nLeft = nMid;
    
26.                 else
    
27.                         nRight = nMid;
    
28.         }
    
29. 
    
30.         return nLength -nMid-1;
    
31. }

复制代码