Теоретически минимум k/ln(k)
достигается при e , а поскольку 3 ближе к e , чем 2, для этого требуется меньше сравнений. Вы можете проверить, что 3/ln(3) = 2.73..
и 2/ln(2) = 2.88..
Причина, по которой бинарный поиск может быть быстрее, заключается в том, что код для него будет иметь меньше филиалов и будет работать быстрее на современных процессорах.