LeetCode: Search Insert Position

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

---

This is just regular binary search. If we found, return its position. If not, return the search start position.

C++ Code:

/*
 * func: search_range_helper
 * goal: binary search for the target
 * @param A: input integer array A
 * @param start: start index
 * @param end: end index
 * @param target: target value
 * return: the index of target
 */
int search_insert_helper(int A[], int start, int end, int target){
    if(start > end){
        return start;
    }
    int mid = start + (end-start) / 2;
    if(A[mid] == target){
        return mid;
    }else if(A[mid] > target){
        return search_insert_helper(A, start, mid-1, target);
    }else{
        return search_insert_helper(A, mid+1, end, target);
    }
    
}

/*
 * func: search_insert
 * goal: find the index if the target is found. If not, return the index where it 
 *       would be if it were inserted in order
 * @param A: integer array A
 * @param n: size of the array A
 * @param target: target value
 * return: the insert position if not found
 */
int search_insert(int A[], int n, int target){
    assert(n > 0);
    return search_insert_helper(A, 0, n-1, target);
}

In Python, it just mimic the function bisect.bisect_left() for list without duplicate elements.

Python Code:

# func: 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.
# @param A: input list A
# @param target: target value
# @return: target position
def search_insert(A, target):
    if not A:
        return 0
    start = 0
    end = len(A)-1
    while start <= end:
        mid = start + (end-start)/2
        if A[mid] == target:
            return mid
        elif A[mid] < target:
            start = mid+1
        else:
            end = mid-1
    return start