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