Бинарный поиск

Гм. Как всё запущено. Сейчас попробую очень по-простому объяснить:
Машина данные представляет в памяти в двоичном коде.
Т.е. число, скажем, 4 будет в виде (дохрена нулей)100.
А текстовый вид предлагает число 4 представить в виде литеры 4 (в виде дохрена_нулей-00111000 в случае ASCII)
Если бинарный формат можно тупо загружать в память и работать, то текст нужно каким-то образом транслировать во что-то машиноприятное.
Это долго и это нужно делать каждый раз.

Индексация, сжатие, оптимизация

Для машины бинарное представление уже является осмысленным. Текстовое содержит смысл только для человека. И вот затраты на трансляцию текстового смысла в бинарное требует дополнительные ресурсы.

Бинарный поиск

Вы будете смеяться©, но в заголовке содержится большая часть ответа.

Бинарный поиск к бинарным данным имеет весьма посредственное отношение.

Потому что данные в них хранятся специальным образом, что позволяет использовать блее быстрые (эффективные) агоритмы поиска. Подробне ты можешь узнать в каком-нибудь курсе лекций под названием «Алгоритмы и структуры данных».

Но зато к формату journald, на который ссылается ОП, он имеет не опосредованное, а самое что ни на есть прямое отношение:

Seeking to an entry by timestamp or sequence number (without any matches) is done via binary search in the entry arrays starting with the header's entry_array_offset field. Since these arrays double in size as more are added the time cost of seeking is O(log(n)*log(n)) if n is the number of entries in the file.

Я подозреваю, что это как-то связано с файловой системой

Кстати, это верное предположение.

Например:
http://www.cs.umb.edu/~henryzlo/cs310/notes/b-trees.pdf

Though B-trees do not improve on normal trees in terms of O(n), they optimize disk usage