C++ using recursion in O(logn) time


  • 1
    G

    Divide the array into parts using mid. There can be two possible options, either first half is sorted or second half is sorted. Then check which part the target belongs and narrow down the search.

      int Util(int A[], int l, int r, int data)
        {
            if(l<=r)
            {
                int mid = l + (r-l)/2;
                if(A[mid] == data)
                    return mid;
                    
                /*check if first half of the array is sorted    */
                if(A[l]<=A[mid])
                {
                    /*Check whether the target belongs to this part of sub array */
                    if(data >=A[l] && data < A[mid])
                        Util(A, l, mid-1, data);
                    else
                        Util (A, mid+1, r, data);
                }
                /* else if the second half is sorted, repeat the same here */
                else
                {
                    if(data > A[mid] && data <= A[r])
                       return Util(A, mid+1, r, data);
                    else
                        return Util (A, l, mid-1, data);
                }
                
            }
            else /* target not found */
                return -1;
        }
        
        int search(int A[], int n, int target) {
            
            return Util(A,0,n-1,target);
        }

Log in to reply
 

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