Search Insert Position - LeetCode

• Return the index if found, otherwise the index where it would be inserted

Key idea

• Standard template, but return left instead of -1
• When the loop exits, left > right, the pointers have crossed
  • right sits just left of where target belongs
  • left sits just right of where target belongs
• So left is exactly the slot target should go into

int searchInsert(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return left;
}

Walkthroughs

• nums = [1,3,5,6], target = 2
  • mid = 1, nums[1] = 3 > 2, so right moves left
  • left > right, loop ends, return left = 1
• nums = [1,3,5,6], target = 7
  • target is bigger than everything, left chases right to the end
  • loop ends, return left = 4