Sorted array rotation

[mailsubhra]

Problem Statement:
Implement the following function, FindSortedArrayRotation,
which takes as its input an array of unique integers that has been sorted
in ascending order, then rotated by an unknown amount X where 0 <=
X <= (arrayLength - 1). An array rotation by amount X moves every
element array to array[(i + X) % arrayLength]. FindSortedArrayRotation discovers and returns X by examining the array.
Consider performance, memory utilization and code clarity and elegance
of the solution when implementing the function.

C++ Prototype

int FindSortedArrayRotation( int
array[], unsigned length )

{

}

My code so far:

Code:

/********************
This program will find the starting value of the array which has been rotated
by X number.
*****/

#include <iostream>
int findSortedRotation(int arr[], int min, int max){
    int len = max - min + 1;
    int midVal = ((len - 1)/2) + min;
    if(len%2 == 0) // If the number is even
    {
             if(arr[midVal] > arr[midVal + 1])
                         return arr[midVal + 1];
    }
    if(len == 2)
    {
           if(arr[min] > arr[max])         
                       return arr[max];
    }
    if(len == 1)
    {
           return arr[max];
    }
    if(arr[min] > arr[midVal])
                return(findSortedRotation(arr, min, midVal));
    else if(arr[midVal + 1] > arr[max])
                return(findSortedRotation(arr, midVal + 1, max));
    else // if the array is already unrotated.
                return arr[min];
}
int main(){
    int intArray [] = {2, 3, 6, 7, 8, 9, 12};
//    int intArray [] = {6, 8, 10, 14, 17, 2, 5};
    int num = findSortedRotation(intArray, 0, 6);
    std :: cout <<"Array rotated at: " << num << "\n";
    getchar();
}

I have tried to use divide and conquer to enhance the performance. The other option could have been something like linear search.
Question 1: Can this algo be further improved?
Question 2: Is it okay to say that the time complexity of the algo is O(logn) as opposed to O(n) for linear search.

Thanks,
mailsubhra.

[myork]

Comment 1: Your function does not have the same signature as required by the problem.
                   You need to write a wrapper that matches the requirements and calls your function.

Comment 2: If you are going to do a binary chop. Are some of the chops going to fail.
                   As a result do you not need a fail condition (ie return -1 if not found in a particula section)?

Comment 3: Would it not look neater to test for length == 1 first?

[mailsubhra]

myork: thanks a lot for the reply.
I have changed the code.
However I could not incorporate your comment no 2. It would be great if you can help me with this.

Code:

/******************************************
This program will find the starting value of the array which has been rotated by X number
***************************/

# include <iostream>
int findSortedRotation(int arr[], int minIdx, int maxIdx){
        int len = maxIdx - minIdx + 1;
        int midVal = ((len - 1)/2) + minIdx;

        if(len == 1)
        {
                return arr[maxIdx];
        }

        if(len == 2)
        {
                if(arr[minIdx] > arr[maxIdx])
                        return arr[maxIdx];
        }

        if(arr[midVal] > arr[midVal+ 1])
        {
                return arr[midVal +1];
        }


        if(arr[minIdx] > arr[midVal])
                return findSortedRotation(arr, minIdx, midVal);
        else if(arr[midVal + 1] > arr[maxIdx])
                return findSortedRotation(arr, midVal + 1, maxIdx);
        else
                return arr[minIdx];
}

int FindSortedArrayRotation(int array[], unsigned length){
        return findSortedRotation(array, 0, length - 1);
}

int main(){
        int intArray[] = {6, 8, 10, 14, 17, 4, 5};
//      int intArray[] = {6, 8, 10, 14, 17, 24, 25};
//      int num = findSortedRotation(intArray, 0, 6);
        int num =  FindSortedArrayRotation(intArray, 7);
        std :: cout << "Number is: " << num << std :: endl;
return 0;
}

Thanks,