количество сравнений бинарного поиска

Если вам нужен точный ответ, то это явно не N log(N) или N log₂(N). Для большинства целых чисел N значения logN и log₂ не являются рациональными, но количество сравнений должно быть целым числом.

Кроме того, точный ответ будет зависеть от деталей реализации алгоритма бинарного поиска. Например, если «сравнение» — это простое отношение, которое возвращает истину и ложь, требуется больше сравнений, чем когда «сравнение» возвращает отрицательное значение, ноль или положительное значение. (В последнем случае вы можете закоротить, когда алгоритм рано нажмет на клавишу.)

Требуется log2 n, чтобы найти каждый, и это нужно сделать n раза, так что n log n получается.

Я бы сказал, что это занимает n log m

Где m — размер массива, поэтому log m найти значение. Затем вы делаете это n раза для n различных целых чисел.

Всего n log m.

Будет не более (2 * log₂n + 1) округленных вниз (таким образом, 7,6 => 7) сравнений для 1 числа.

Когда мы находим какое-то число в массиве, сначала мы проверяем, является ли оно тем, которое мы ищем. (== первое сравнение). После этого проверяем, меньше (или больше) (второе сравнение).

Чтобы найти число, мы должны обработать не более log₂n чисел.

И мы должны сделать последнее сравнение с последним числом, чтобы убедиться, что это именно оно.

Таким образом, поиск 16 в [1..16] потребует 2*log₂16 + 1 = 9 сравнений (при условии, что мы попадаем на эти числа: 8, 12, 14, 15, 16). И поиск 10 в [1..10] займет 2 * log₂10 + 1 = 7,6 => 7 (предполагая, что мы попадаем на эти числа: 5, 8, 9, 10).

Таким образом, для n чисел их будет не более чем в n раз больше.

Спасибо за ваши комментарии, теперь я ясно. Я думаю, что то, что сказал Стивен С, правда. Я думаю, что мы не можем выработать формулу для этого вопроса, если у нас нет точного значения. Однако, если n=2^n-1, например 511(2^9-1), это легко вычислить. Для 511 общее количество сравнений = 1x1 + 2X2 + 3X4 + 4X8 + ​​5X16 + 6X32 + 7X64 + 8X128 + 9X256 = 4097.