Не понимаю, в чем проблема вообще. Забудьте, что это строки или числа. Все что нужно для бинпоиска - это уметь спрашивать < или = искомая штука и штука в массиве по заданной позиции.
В питоне есть массивы (доступ по индексу) и строки он сравнивает автоматом через операторы == и <.
Т.е. можно написать тот же абсолютно код, что и для бинпоиска по числам и он будет работать на строках. Правда, надо помнить, что сложность у бинпоиска по строкам будет не O(log n), а O(L log n), где L - максимальная длина строк.
