Допустим, мы массив {-2, 8, 13, 22, 25, 25, 38, 42, 51, 103}двоичного поиска и дублирует
Когда бинарный поиск делит его на 2 в первый раз, что будет считаться средним значением?
Мое собственное предположение - это второе значение с именем 25, потому что только тогда поиск знает, что он идентичен.
Я считаю, что всегда пытается найти середину на
(0+n)/2 = (0+9)/2 = 4(Integer)
В вашем случае.
Так что если вы хотите найти 25 себя, то согласно алгоритму вы найдете в нижней граничной группе позицию 4 сначала в качестве совпадения.
Среднее значение первое 25 число.
Ваш первый вызов двоичного поиска выглядит примерно так: binarySearch (a, 1, a.length), где «a» - ваш массив.
Длина вашего массива равна 10, поэтому m = ((10-1) +1)/2 = 5 позиция в массиве.
Затем вы звоните BinarySearch (1, м) и применить тот же метод для этого массива (первая половина от первоначально массива) -2, 8, 13, 22, 25
Эй, спасибо за ответ. Что такое +1 в m = ((10-1) +1)/2? – Rasmus
Это математика. Чтобы найти lentgh от a до b, вы делаете (b-a) +1. Например, длина вашего массива равна 10. Первый элемент находится в первой позиции (a = 1), а последний элемент находится на 10 позиции, поэтому длина 10-1 + 1 = 10 – Ciprian
Другой пример: m = 5, поэтому вызов binarySearch для второй половины вашего массива - binarySearch (a, m + 1, a.length) = binarySearch (a, 6,10), и этот вызов будет работать над этим массивом {25, 38, 42, 51, 103}; чтобы найти m для этой половины вашего массива, вы должны знать, что это (кто 5, но вы должны это выяснить): 10-6 + 1 = 5 и m будет 5/2 = 2 – Ciprian
Высокий, спасибо. :) – Rasmus
Рад помочь :) –