Leetcode – Search Insert Position

Name: Search Insert Position
Difficulty: Easy
Description: Return the index of target, or where target should be in a sorted array

Example:

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

The solution was quite simple, but I complicated it by initially using a binary search, and then adding conditions to return quickly in certain obvious cases. Based on the data which drove the tests, this gave the best performance:

int searchInsert(vector<int>& nums, int target) {
    for(auto i = nums.begin(); i < nums.end(); ++i) {
        auto x = *i;

        if (x >= target) return static_cast<int>(i - nums.begin());
    }

    return static_cast<int>(nums.size());
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s