There is three corner cases must be handled if we don’t find target in nums:

  1. Return r + 1 if target is greater than right.
  2. Or return mid + 1 if target is greater than mid.
  3. Otherwise return mid.
class Solution {
public:
	int searchInsert(vector<int>& nums, int target) {
		int l = 0, r = nums.size() - 1;
		int mid = r / 2;
		while (l != r) {
			mid = l + (r - l) / 2;
			if (target == nums[mid]) {
				return mid;
			}

			if (target < nums[mid]) {
				r = mid;
			} else {
				l = mid + 1;
			}
		}
		if (target > nums[r]) {
			return r + 1;
		}
		if (target > nums[mid]) {
			return mid + 1;
		}
		return mid;
	}
};