Binary Search Lower Bound: First Element Not Less Than Target
Problem Statement
Given a sorted array of integers `nums` and an integer `target`, implement `lower_bound(nums, target)`:
Return the index of the **first element** in the array that is **greater than or equal to** `target`.
If all elements in the array are strictly smaller than `target`, return the length of the array `n`.
You must write an algorithm with `O(log n)` runtime complexity.
### Input Format
- First line contains space-separated integers representing `nums`.
- Second line contains an integer `target`.
### Output Format
- Print a single integer representing the lower bound index.
### Constraints
- `1 <= nums.length <= 10^5`
- `-10^9 <= nums[i], target <= 10^9`
- `nums` is sorted in non-decreasing order.
Sample Cases
Example 1Sample Case
Input: 1 2 4 4 5 6 8
4
Output: 2
Example 2Sample Case
Input: 1 2 4 4 5 6 8
7
Output: 6
Example 3Sample Case
Input: 1 2 4 4 5 6 8
9
Output: 7
Example 4Sample Case
Input: 1 2 4 4 5 6 8
3
Output: 2
Constraints
Runtime Limit: 2000 ms per test batch
Memory Limit: 256 MB
Standard I/O stream reading
Official submissions are evaluated against hidden test cases on the server to verify time & memory complexity.