Я подозреваю, что вы неправильно истолковываете значение медианы как элемента в позиции (n - 1) / 2. Дело не в том, что медианный элемент - это элемент, который является точной позицией в массиве. Скорее, это элемент, который был бы в этой позиции, если бы вы сортировали массив.
Например, рассмотрим массив
[31, 41, 59, 26, 53, 58, 97]
и представьте, что мы хотим сделать число 93 медианным. Давайте подумаем о том, что нам нужно сделать, чтобы это произошло. Для начала, чтобы значение 93 было медианой, нам нужно добавить его в массив, как показано здесь:
[31, 41, 59, 26, 53, 58, 97, 93]
^^
Теперь, в каком положении был бы 93, если бы мы сортировали массив? Давайте на самом деле отсортируем массив, чтобы узнать:
[26, 31, 41, 53, 58, 59, 93, 97]
^^
Обратите внимание, что он находится в позиции 6 в массиве. Это не середина массива, и для того, чтобы этот элемент оказался в средней позиции, нам нужно было бы вставить еще несколько значений, которые следуют после 93, достаточно, чтобы заполнить массив так, чтобы 93 находился посередине. Например, мы могли бы добавить несколько дополнительных 99-х, как показано здесь:
[26, 31, 41, 53, 58, 59, 93, 97, 99, 99, 99, 99, 99]
^^ ^^ ^^ ^^ ^^ ^^
Так что в этом случае нам нужно было бы добавить всего пять элементов в массив, чтобы получить медиану для 93.
Теперь, вот вопрос для рассмотрения: почему мы получили ответ пять? Причина этого заключается в следующем. Следуя обозначениям вашего алгоритма, мы должны убедиться, что число элементов меньше 93, которое мы обозначим m, равно количеству элементов больше 93. Число элементов больше 93, которые в настоящее время существуют в массиве, задаются как n - m, так как это все элементы массива, минус те, которые меньше 93.
Итак, давайте предположим, что мы добавляем 93 непосредственно к массиву вместе с k элементами больше 93 к массиву, чтобы попытаться поместить 93 в среднюю позицию. Из того, что мы сказали выше, мы должны иметь, что число элементов меньше 93 (m) должно быть на один меньше, чем количество элементов в общем массиве больше или равно 93 (n - m, элементы уже больше или равны 93, плюс k, количество добавленных нами дополнительных элементов). Термин -1 здесь объясняет тот факт, что, когда мы делаем деление для вычисления средней позиции, мы округляем вниз. Это означает, что у нас будет
m - 1 = n - m + k
или, что
k = 2 м - n + 1
И, эй, смотри! Это 2*m - n + 1, что мы и возвращаем в случае, когда m & ge; n - m, что означает, что число больше или равно более чем половине элементов массива.
С другой стороны, давайте вернемся к нашему исходному массиву, как показано здесь:
[31, 41, 59, 26, 53, 58, 97]
Представьте, что мы хотим сделать 27 медианным элементом. Начнем с добавления 27, как показано здесь:
[31, 41, 59, 26, 53, 58, 97, 23]
^^
Теперь, если мы отсортируем элементы, мы получим следующее:
[26, 27, 31, 41, 53, 58, 59, 97]
^^
Это не в средней позиции, поэтому нам нужно добавить еще несколько элементов для заполнения массива. Давайте представим, что добавим кучу меньших элементов для раскладки, например:
[13, 13, 13, 13, 26, 27, 31, 41, 53, 58, 59, 97]
^^ ^^ ^^ ^^ ^^
Похоже, нам снова нужно пять элементов. Это почему? Как и раньше, предположим, что мы добавляем k элементов в массив. Нам нужно иметь это
количество элементов меньше 27 (m) плюс количество элементов, добавленных в (k), на один элемент меньше
количество элементов больше или равно 27 (n - m), минус один, потому что вновь добавленные 27 будут считаться одним из элементов, большим или равным себе.
Другими словами, нам нужно
m + k = n - m,
или что
k = n - 2 м.
Это дает нам n - 2 * m, который составляет второй случай.
Итак, подведем итог - математика здесь возникает потому, что мы пытаемся заполнить массив так, чтобы сторона, содержащая добавляемое число, имела ту же длину, что и меньшая сторона, и математика того, как это сделать, зависит от того,мы находимся в первой или второй половине массива.
Надеюсь, это поможет!