So it's a psychological problem.
I think it's best to just duplicate the code and reverse some indices. It's not like the search-code will change all the time, and changing in two places isn't a _real_ problem.
I seldom use reverse search though, and search(reverse()) works fine for me unless the string/array is huge, but even if it is, the reverse takes little time compared to the search.
An odd alternative would be to let search'es last element be negative so that search("foo", -1) starts with the last position and goes backwards. But... On the other: hand -1 could mean "start with the last position and go forward" too, and that's maybe better.