In fact, no, hang on, your method doesn't even work. I'm not just after an occurrence of the needle; I'm after the rightmost. So if there are two occurrences, one in the left half and one straddling the halfway point, then the condition in your "if" will not be fulfilled and we'll recurse blindly into the left half, completely missing the rightmost real occurrence in favour of the rightmost one that didn't hit a special case.