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

Question

Какое общее число сравнений необходимо, чтобы найти все n отсортированных целых чисел в массиве с помощью бинарного поиска? Я думаю, что число - n log ₂ n (2 - основание), но я не уверен. Как вы думаете?

Answer 1

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

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

Answer 2

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

Answer 3

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

Answer 4

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

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

Чтобы найти число, мы должны обработать не более 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 раз больше.

Answer 5

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

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

Итого n log m.