Move right when the pair sum is too large
Updated
If a[L]+a[R] > target, every pair using this R and a larger left is even larger. R -= 1. L stays.
What to focus on
After the move R is the old R-1 and L is unchanged. You discard a[R] as a right partner. The array is already sorted.
Worked examples
need 8
a = [1, 4, 9], target=8, L=0, R=2- L=0, R=2
- 1+9=10 > 8
- R -= 1
Result: L=0, R=1
need 5 inner
a = [1, 4, 9], target=5, L=1, R=2- L=1, R=2
- 4+9=13 > 5
- R -= 1
Result: L=1, R=1
dups
a = [1, 4, 4, 9], target=8, L=0, R=3- L=0, R=3
- 1+9=10 > 8
- R -= 1
Result: L=0, R=2
Try it
Write moveRightIfLarge(a, L, R, target). a is a sorted array of integers. L is the left index. R is the right index. target is the pair sum. a[L]+a[R] > target. Do R -= 1. Print new L, R. Return nothing. On [1, 4, 9] from (0, 2) target 8 and from (1, 2) target 5, and on [1, 4, 4, 9] from (0, 3) target 8.
a is sorted non-decreasing, length ≥ 2. a[L]+a[R] > target. L < R.