用递归求数组最大值的位置

1. 
   
2. public int getMaxIndex(int[] array) {
   
3.         if (array == null) {
   
4.                 return -1;
   
5.         }
   
6. 
   
7.         int maxIndex = getMaxIndexRecursive(array, array.length - 1);
   
8. 
   
9.         return maxIndex;
   
10. }
    
11. 
    
12. private int getMaxIndexRecursive(int[] array, int lastIndex) {
    
13.         int maxIndex;
    
14. 
    
15.         if (lastIndex < 0) {
    
16.                 maxIndex = -1;
    
17.         } else if (lastIndex == 0) {
    
18.                 maxIndex = lastIndex;
    
19.         } else {
    
20.                 int subMaxIndex = getMaxIndexRecursive(array, lastIndex - 1);
    
21.                 maxIndex = array[subMaxIndex] >= array[lastIndex] ? subMaxIndex : lastIndex;
    
22.         }
    
23. 
    
24.         return maxIndex;
    
25. }
    

复制代码

检查边界条件：数组为null，或者index为负的情况下，返回-1

crazyai 发表于 2013-8-7 12:53
这个复杂度是O(n)的吧，T(n)=2T(n/2)+O(1)，由主定理得O(n)
从另一方面想，从无序数组中找到最大值下标， ...

我也觉得应该是O(n)

        public static int findIndex(int[] data, int i){
                if(data.length - 1 == i)
                        return i;
                int preMaxIndex = findIndex(data, i + 1);
                return data[i] > data[preMaxIndex] ? i : preMaxIndex;
        }

int max(const int a[], int n)
{
    assert(n > 0);
    if (n == 1)
        return 0;
    int preMax = max(a, n - 1);
    return a[n - 1] > a[preMax] ? n - 1 : preMax;
}
int main()
{
    int a[5] = {1,3,5,7,9};
    cout << max(a,sizeof(a)/sizeof(a[0])) << endl;
    return 0;
}
我的思想是先遍历前n-1个元素，再与当前元素比较。