You can avoid O(N) calculation in the worst case. If you have M numbers which don't equal to the constant [C, C, ..., C, A1, A2, ..., AM, C, ..., C], all this numbers have to be in succession. So it would be enough to check only every Mth number for finding the element which is not equal to C. Of course, we don't know M, but we can try M=N, M=N/2 and so on. As the result, the complexity will be O(N/M).
My code in Java
Find Minimum in Rotated Sorted Array II