В бинарном поиске, как компьютер выбирает середину и когда остается только два элемента

Question

Я читал некоторые вопросы по стеку и другие блоги по этому вопросу.

Большинство из них объясняют, как выбрать среднюю точку, используя:

1. low + (high - low)/2
2. (low + high)/2, round down to integer.

из Выбор середины бинарный поиск и https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/binary-search

Ни один из них не имеет смысла.

говорят, что у меня есть список в форме

lst = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

используя 1. средняя точка = 46.5 и 2. средняя точка = 50.5, округленная до 50.

обе средние точки даже не в моем списке.

Более того, когда есть только 2 элемента какую из них выбрать в качестве средней точки?

Answer 1

Переменные low и high не относятся к элементам списка или массива. Они ссылаются на индексы списка или массива. Таким образом, средний элемент не будет определяться как: low + (high - low)/2 или (low + high)/2 (округление до целого числа), а скорее как lst[low + (high - low)/2] или lst[(low + high)/2]

Answer 2

Бинарный поиск low / high относится к ndexes, а не к значениям массива.
Так что в вашем случае mid index равен (0 + 9) /2=4.

В случае длины 2 вы получите средний индекс 0, правая часть будет иметь один элемент, левый пустой (или содержит единственный 0-й элемент, если средний не рассматривается отдельно).

Answer 3

1. low и high относятся к индексам списка, а не к их значениям

2. , если есть два элемента, потребуется low и high, которые будут равны 0 и 1, а затем выполните low + (high - low)/2, что будет равно 0 + (1 - 0)/2, что дает нам 0.5, в зависимости от вашего алгоритма, вы можете округлять в большую или меньшую сторону, так как вы выбрали округление в меньшую сторону у нас есть значение 0, которое будет индексом средней точки, которая будет выбрана