Given a list nums sorted in non-decreasing order and an integer target, return the index at which
target would have to be inserted so the list stays sorted. If target already occurs, return the index
of its first occurrence.
Examples
Input: nums = [1, 3, 5, 6], target = 5
Output: 2
Input: nums = [1, 3, 5, 6], target = 2
Output: 1
Explanation: 2 goes between 1 and 3.
Input: nums = [1, 3, 5, 6], target = 7
Output: 4
Constraints
0 <= len(nums) <= 10**6-10**9 <= nums[i], target <= 10**9- Your solution must run in
O(log n)time; a linear scan is too slow for the largest tests.
Goals
- Write a leftmost binary search with lo/hi that converge on an index
- Handle targets smaller or larger than every element