35. Search Insert Position

#binary-search

Problem

Search Insert Position - LeetCodeLeetCode

Intuition

Since we need to find the position at which an element needs to be inserted, we need to find the lower bound CN: Implement Lower Bound

Time Complexity

O(log n)

Space Complexity

O(1)

Solution

class Solution {
    public int searchInsert(int[] nums, int target) {
        // Need to find the ceiling of the target.
        // We need to find the index where we can actually insert the target, that is
        // find the immediate largest number for the given target
        int low = 0, high = nums.length-1;
        int result = nums.length;

        while(low <= high) {
            int mid = low + (high-low)/2;

            // When we find nums[mid] >= target, then we need to search towards left,
            // as we are trying to find the immediate largest number.
            // Since we already found a larger number, we need find the smaller larger
            // number. In a sorted array you can find smaller number towards your left, 
            // so update the search space to look at left by setting high = mid -1;
            if(nums[mid] >= target) {
                result = mid;
                high = mid-1;
            } else {
                low = mid + 1;
            }
        }
        return result;
    }
}