Я предполагаю, что это домашнее задание, поэтому вместо простого ответа я дам подсказку. Я также предполагаю, что вас попросили найти относительно точный ответ, а не просто большой ответ.
Думайте об этом так: каждый раз, когда вы делаете сравнение, вы вдвое сокращаете пространство поиска. Если пространство поиска имеет размер S, то вероятность нахождения записи на следующей итерации равна 1 / S. Если C обозначает количество сравнений, то P (найти его при сравнении C) = P (не найти в