Given a sorted array nums (in non-decreasing order) and an integer target, return the lowest index at which target could be inserted to keep nums sorted (also known as the lower bound). If target already exists in nums, return the index of the FIRST such occurrence. If target is greater than every element, return the length of the array. You must implement the search recursively (e.g., via a recursive binary-search variant).
Input: A sorted integer array nums and an integer target.
Output: Return an integer in the range [0, nums.length].
Input: [1,3,5,7], 4
Output: 2
Explanation: 4 would be inserted at index 2 to keep order: [1,3,4,5,7].Input: [1,3,5,7], 1
Output: 0
Explanation: 1 already at index 0; first match returned.Input: [1,3,5,7], 10
Output: 4
Explanation: 10 is greater than all elements; insert at end (index 4).1 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9nums is sorted in non-decreasing order-10^9 <= target <= 10^9