The brute force solution to this problem is accepted, since traversal the array is only o(n) time.
The brute force solution is accepted.

It is difficult to differentiate between O(n) and O(log n) algorithm in general, as @loick already answered nicely here. Since the O(n) algorithm traverses the array in sequence, it is extremely fast as the cache hit rate is going to be high.
On the other hand, the O(log n) binary search algorithm has more unpredictable array index access, which means it will result in more cache misses.
Unless n is extremely large (up to billions, which is unpractical in this case), there could be a chance that the Brute Force O(n) algorithm is actually faster.

EDIT : Kindly ignore my comment, its incorrect!
I don't think a solution better the
O(n)
is possible.To do binary search in the rotated array, one needs to find the pivot at which rotation takes place. After find the pivot, it is possible to do binary search in the two sorted arrays separately. But finding the pivot can be
O(n)
worst case  say if the array was not rotated, implying no pivot element and then one would have to do a binary search in the whole array.


Differentiating between O(n) and O(n logn) is difficult because logn increases very slowly [As is mentioned in the reference link]. It as same as differentiating O(1) and O(logn) algorithms.
However, O(n) and O(log n) algorithms can be easily differentiated. n~10^5 would be more than enough.

My solution is log N.
I have two nested recursive binary searches. The internal is a regular binary search.
The top level one is an altered binary search (a pivot search) that does: 1 check if the first element is the target, return if so.
 2 check if the first element is minor than the last, than we assume that everything in the middle is sorted. Then call binary search recursive function and return its result.
 3 split the section into two parts choosing a pivot in the middle.
 4 test the right half and return only if the target is found.
 5 test the left part and return its result.
Point 2 is a variant on the traditional binary search and also the fact that we have to perform the search on both halves at points 4 and 5.
Is logN but have two status:
 recursive pivot search
 recursive binary search

public class Solution { public int search(int[] A, int target) { return search(A,target,0,A.length1); } public int search(int[] A, int target, int low, int high) { int mid=(low+high)/2; if(A[mid]==target) return mid; if(low>high) return 1; if(A[low]<=A[mid]) { if(target>=A[low]&&target<A[mid]) return search(A,target,low,mid1); else return search(A,target,mid+1,high); } else if(A[mid]<=A[high]) { if(target>A[mid]&&target<=A[high]) return search(A,target,mid+1,high); else return search(A,target,low,mid1); } return 1; }
}
I used binary search here, comparing to common binary search method it adjust a little. When making the judgement which side to search, it differs in which side is ordered. Because a rotate array must be normally ordered in one side.