Why a recursive version is faster than a iterative version?


  • 0
    O

    The problem itself is not that hard and I tried to solve it both with and without recursion. Both solutions were accepted and I was expecting that the iterative version should perform better. However, it was the opposite. The recursive version was almost 50 percent faster. I appreciate it a lot if anybody can point out why the recursive version is faster? Below are the codes: (The algorithms behind the scene are identical, just plain binary search for both)

    The recursive version. The run time is 245 ms.

    public int searchInsert(int[] A, int target) {
        return binarySearch(A,0,A.length-1,target);
    }
    private int binarySearch(int[] A, int low, int high,int target) {
    	if (low>high) return low;
    	else{
    		int mid=low+(high-low)/2;
    		if (A[mid]==target) return mid;
    		else if (A[mid]>target) return binarySearch(A,low, mid-1,target);
    		else return binarySearch(A,mid+1,high,target);
    	}
    }
    

    The iterative version. The run time is 357 ms.

     public int searchInsert(int[] nums, int target) {
       int low=0, high=nums.length-1;
        while (low<=high){
        	int mid = low + (high-low)/2;
        	if (nums[mid] == target) return mid;
        	else if (nums[mid] > target) high = mid-1;
        	else low = mid+1;
        }
        return low; 
    }

Log in to reply
 

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