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


  • 0
    I
    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!


  • 0
    I

    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


  • 2
    H

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


Log in to reply
 

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