# Can I write code in recursion way for this problem?

• 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);
}
}``````

• 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;
}
};``````

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