Really interesting post and good debugging work. A couple of take-aways:
1. This is one reason it's a good idea to use signed ints for lengths even though they can never be negative. Signed 64-bit ints have plenty of range for any array you're actually going to encounter. It may also be evidence that it's a good idea for mixed signed/unsigned arithmetic to produce signed results rather than unsigned: signed tends to be value-correct for "small" values (less than 2^63), including negative results; unsigned sacrifices value-correctness on all negative values to be correct for very large values, which is a less common case – here it will never happen since there just aren't strings that large.
2. If you're going to use a fancy algorithm like two-way search, you really ought to have a lot of test cases, especially ones that exercise corner cases of the algorithm. 100% coverage of all non-error code paths would be ideal.
Regarding 2., I'm going to assume they have at least some unit tests.
It's not clear that even 100% coverage would have picked up this bug, since it doesn't automatically appear as a result of taking a particular code path.
I think that comparing to a naive algorithm on a large number of strings, or using a fuzzing tool, might be helpful, but this might also slow down the test suite excessively.
I find unit tests are a bit like good form at the gym. Whenever someone gets injured, they think back to the last exercise they did and find some imperfection in their form. They then attribute their injury to not using perfect form. Similarly, whenever a bug appears, there is a tendency to find a unit test that would have caught the bug, and therefore attribute it to insufficient testing.
The real value of testing (and good form) can only be demonstrated by having a criteria for good testing and seeing if following this reduces the number of bugs.
They did have some tests, obviously not enough though.
I don't think it is the number but the depth. Something like QuickCheck would help. Or, having simpler code.
https://github.com/BurntSushi/quickcheck
Would be pretty cool to see someone hook it up to the standard library tests.