Approach

1. Use binary search on a half-open candidate interval [left, right), starting at [0, len(values)).
2. If values[mid] is less than target, discard through mid by moving left to mid + 1. Otherwise move right to mid, keeping equal values in the candidate interval.
3. When left equals right, it is the first position whose value could be at least target. Return it only if it is in bounds and equals target; otherwise return -1.

Why it works

Every discarded position before left is strictly smaller than target, while narrowing the right boundary on equality preserves the possibility of an earlier match. On convergence, no matching position can precede left. The final bounds/equality check distinguishes an actual match from the insertion position for an absent target.

Complexity

O(log n) time for nonempty input and O(1) auxiliary space. Empty input is handled in O(1). The input remains unchanged.

Edge cases to check

• Empty input returns -1 without indexing it.
• Duplicates require continuing left after equality rather than returning the first midpoint match.
• A target below every value, between present values or above every value may have an insertion position but still returns -1.