Can I write code in recursion way for this problem?


  • 0
    S

    I want to know what problems I must use iteration way..
    If I write my code in this way, is it okay?

    public int[] searchRange(int[] A, int target) {
       
        return searchRange(A,target,0,A.length-1);
    }
    
    public int[] searchRange(int[] A, int target, int first, int last){
        int[] result=new int[2];
        if(first>last){
            result[0]=-1;
            result[1]=-1;
            return result;
        }
        int mid=(first+last)/2;
        if(A[mid]==target){
           int[] left= searchRange(A,target,first,mid-1);
           int[] right= searchRange(A,target,mid+1,last);
           result[0]=(left[0]==-1)? mid:left[0];
           result[1]=(right[1]==-1)?mid:right[1];
           return result;
        }else if(A[mid]<target){
            return searchRange(A,target,mid+1,last);
        }else{
            return searchRange(A,target,first,mid-1);
        }
    }

  • 0
    V

    Above program is recursive and has space complexity of O(logn) due to call stack space used for recursion, which can be avoided by using an iterative implementation.

    class Solution {
    public:
       int searchBoundary(int A[], int n, int target, bool isLower)
    {
        int start = 0;
        int end = n-1;
        if (n == 0)
            return -1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (target < A[mid])
                end = mid - 1;
            else if (target > A[mid])
                start = mid + 1;
            else if (isLower) {
                end = mid;
            } else {
                if (mid == start) {
                    return (A[end] == target) ? end : start;
                }
                start = mid;
            }
         }
        if (A[start] == target)
            return start;
        else
            return -1;
    }
    
    vector<int> searchRange(int A[], int n, int target) {
        vector<int> result{-1, -1};
        int lower = searchBoundary(A, n, target, true);
        if (lower != -1) {
            result.clear();
            result.push_back(lower);
            result.push_back(searchBoundary(A, n, target, false));
        }
        return result;
    }
    };

Log in to reply
 

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