[LeetCode] Search Insert Position

The basic idea is to use binary search: keep two pointers l and r for the current search range, then find the middle element nums[mid] in this range. If nums[mid] < target, we knowtarget should at least be inserted after nums[mid], so we update l = mid + 1. Otherwise, update r = mid.

The code is as follows. Note that we initialize r = n instead of n - 1, which easily handles the case that target needs to be inserted after all the elements of nums.

 1 class Solution {
 2 public:
 3     int searchInsert(vector<int>& nums, int target) {
 4         int n = nums.size(), l = 0, r = n;
 5         while (l < r) {
 6             int mid = (l + r) / 2;
 7             if (nums[mid] < target) l = mid + 1;
 8             else r = mid;
 9         }
10         return l;
11     }
12 };

In fact, this is just the sub-routine search in Solution 2 of Stefan's post. Thank Stefan for posting such a nice article!

Well, the system lower_bound may also be used, which just takes 1 line :-)

class Solution { 
public:
    int searchInsert(vector<int>& nums, int target) {
        return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
    }
};