Search Insert Position — Left Boundary for Insert Index

Problem 303 · Search Insert Position

Difficulty: Easy · Pattern: Left Boundary

Return the index where target is found or would be inserted.

Solutions

# Python
def searchInsert(nums, target):
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = lo + (hi-lo)//2
        if nums[mid] < target: lo = mid+1
        else: hi = mid
    return lo

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

Complexity

Time: O(log n)
Space: O(1)

Note

hi = nums.length (not n-1) to handle inserting at end.