# What is the time complexity of this algorithm ? O(n) ? O(logn) ?

• ``````public class Solution {
public boolean search(int[] A, int target) {

if (A==null)
return false;
int mid = A.length/2;

if (A[mid]==target)
return true;
if (A.length<=1)
return false;
if (A[0]<A[mid])
{
if (target<A[mid] && target >=A[0])
return search(arrayResize(A,0,mid-1),target);
else
return search(arrayResize (A,mid+1,A.length-1),target);
}
else if (A[0]>A[mid])
{
if (target>A[mid] && target <A[0])
return search(arrayResize (A,mid+1,A.length-1),target);
else
return search(arrayResize(A,0,mid-1),target);
}
else
return search(arrayResize (A,mid+1,A.length-1),target) || search(arrayResize(A,0,mid-1),target);

}
public int[] arrayResize(int[] A, int left,int right)
{
if (left>right)
return null;
int[] B = new int[right-left+1];
int now=0;
for (int i=left;i<=right;i++)
{
B[now] = A[i];
now++;
}
return B;
}
}
``````

I tried to use recursive to search both ways when encounters A[0]==A[mid], but not sure about the complexity of this algorithm.

Thanks!

• Hmm.. maybe it's still in the O(n), because in worst case, it still need to traverse all elements in the array, like [1,1,1,1,1], 2

• although the expected time complexity is T(lg n), the worst case is T(n). So it's O(n).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.