Search Insert Position

Problem: Search Insert Position

Simple binary search solution. We want to find the rightmost number which is smaller than target.

Code in Python:

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        l, r = 0, len(nums)
        while l < r and nums[r-1] >= target:
            mid = (l+r)/2
            if nums[mid] == target: return mid
            if nums[mid] < target: l = mid+1
            else: r = mid
        return r

Code in Java:

public class Solution {
    public int searchInsert(int[] nums, int target) {
        int res = 0, n = nums.length;
        if (n == 0) return res;

        int l = 0, r = n, m;
        while (l < r) {
            m = (l + r) / 2;
            if (nums[m] == target) return m;
            if (nums[m] < target) {
                if (l == m) return m+1;
                l = m;
            }
            else r = m;
        }
        return l;
    }
}