Search Insert Position

Practice Link

Given a sorted array of distinct integers 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 must write an algorithm with O(log n) runtime complexity.

Examples#

Input: nums = [1,3,5,6], target = 5
Output: 2

Input: nums = [1,3,5,6], target = 2
Output: 1

Input: nums = [1,3,5,6], target = 7
Output: 4

Brute Force#

Walk the array from the left and return the first index where nums[i] >= target. If the target is present, that is its index; if not, it is the first larger element — exactly where the target would be inserted to keep the array sorted. If every element is smaller than the target, it belongs at the end, so return n. This is O(n), so it fails the O(log n) requirement, but it defines precisely what we are looking for: the lower bound of target.

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();

        for(int i = 0; i < n; i++){
            if(nums[i] >= target)
                return i;
        }

        return n;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)

Binary Search#

Because the array is sorted, the lower bound can be found by halving the search range. Run standard binary search: if nums[mid] == target, record mid and stop. Otherwise move low right when nums[mid] < target, or high left when it is larger. If the loop ends without a match, low has crossed high and sits exactly where the target would be inserted — every element left of low is smaller and every element from low onward is larger. So return res when found, otherwise low.

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();

        int low = 0, high = n-1;
        int res = -1;
        while(low <= high){
            int mid = low + (high-low)/2;

            if(nums[mid]==target)
            {
                res = mid;
                break;
            }
            else if(nums[mid] < target){
                low = mid+1;
            }else{
                high = mid-1;
            }
        }

        return res == -1 ? low : res;
    }
};

Time Complexity: O(log n)

Space Complexity: O(1)