[LeetCode] Search Insert Position

Problem Statement (link):

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

Analysis:
It's obvious we can use binary search to find the correct position. A little bit tweaking can make code much cleaner, see below.

The time complexity of this binary search is O(log n).

Code:

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        if (n==0) return 0;
        return recur(A, n, 0, n-1, target);
    }

    int recur(int A[], int n, int st, int ed, int target) {
        if (st>ed) return st; // when not found the same value in array

        int mid=(st+ed)/2;
        if (A[mid]==target) return mid;
        else if (A[mid]>target)
            recur(A, n, st, mid-1, target);
        else
            recur(A, n, mid+1, ed, target);
    }
};