Scan from left for a misplace
Updated
From L, while L ≤ R and a[L] should stay on the left, L++. Stop on the first a[L] that should sit on the right, or when L passes R.
What to focus on
L only increases. The scan does not swap. After it, either L > R (done) or a[L] is a left-side offender.
Worked examples
skip a zero
a = [0, 1, 0, 9], zeros left, L=0 R=3- a[0]=0 stays left
- L 0→1
- a[1]=1 should be right
Result: L=1 misplace 1
skip evens
a = [4, 1, 9], evens left, L=0 R=2- a[0]=4 even
- L 0→1
- a[1]=1 odd
Result: L=1 misplace 1
none
a = [0, 1, 9], zeros left, L=0 R=0 after R moved- a[0]=0 stays left
- L 0→1 > R
Result: no left misplace
Try it
Write scanLeftMisplace(a, L, R). a is an array of integers. L is the left index. R is the right index. L only increases. Return L. The scan does not swap. Zeros-left on [0, 1, 0, 9] starting L=0. Evens-left on [4, 1, 9]. Zeros-left on [0, 0, 1, 9].
a is nonempty. L and R are in-range with L ≤ R. A left-side offender exists in [L, R].