Implement binary search for boundary index

Given a sorted integer array nums (length n) and an integer target t, return the index of the first element in nums that is greater than or equal to t. If no such element exists, return -1. Provide both iterative and recursive implementations, handle duplicate values correctly, and analyze time and space complexity. Explain how you would adapt your solution to find the last element less than or equal to t.

Implement binary search for boundary index

Given a sorted (non-decreasing) integer array nums of length n and an integer target t, return the index of the first element in nums that is greater than or equal to t (the lower bound). If no such element exists, return -1.

With duplicate values, you must return the index of the FIRST (leftmost) qualifying element, not just any matching index. The solution should run in O(log n) time.

Examples:

• nums = [1, 3, 5, 7], t = 4 -> 2 (the first element >= 4 is 5 at index 2)
• nums = [1, 2, 4, 4, 4, 8], t = 4 -> 2 (leftmost 4)
• nums = [1, 2, 3], t = 5 -> -1 (no element >= 5)

Follow-up (discuss, not coded): how would you adapt the same template to find the index of the LAST element less than or equal to t? (Search for the upper boundary instead: track the rightmost index whose value <= t.)

Constraints

• 0 <= n <= 10^5
• nums is sorted in non-decreasing order
• -10^9 <= nums[i], t <= 10^9
• Return -1 when every element is strictly less than t (including the empty-array case)

Hints

1. Use a half-open search interval [lo, hi) where lo = 0 and hi = n. This lets you cleanly represent the 'insertion point' when no element qualifies.
2. On each step, if nums[mid] >= t the answer could be mid or to its left, so move hi = mid; otherwise move lo = mid + 1. Never discard a candidate by setting hi = mid - 1.
3. After the loop, lo is the count of elements < t. If lo == n, no element is >= t, so return -1; otherwise lo is the leftmost qualifying index.
4. For the follow-up (last element <= t), mirror the logic: find the first index whose value > t, then subtract one (and check it is in bounds).