Изменения
→Варианты решения
Рассмотрим следующую ситуацию: пусть у нас есть элемент <tex>a[i]</tex> из массива <tex>A</tex> и элемент <tex>b[j]</tex> из массива <tex>B</tex> и они связаны неравенством <tex>b[j - 1] < a[i] < b[j]</tex>. Тогда <tex>a[i]</tex> есть <tex>(j + i + 1)</tex>-ый порядковый элемент после слияния массивов. Это объясняется тем, что до <tex>a[i]</tex>-ого элемента идут <tex>(j - 1)</tex> элемент из массива <tex>B</tex>, <tex>i</tex> элементов из массива <tex>A</tex> (включая сам элемент <tex>a[i]</tex>) и так как индексация массивов начинается с нуля, то необходимо прибавить еще <tex>2</tex>. В итоге получаем <tex>(j - 1) + i + 2 = j + i + 1</tex>. Принимая это во внимание, будем выбирать <tex>i</tex> и <tex>j</tex> таким образом, чтобы <tex>j + i + 1 = k</tex>.
Подведем итоги вышесказанногопромежуточный итог:
# Инвариант <tex>j + i = k - 1</tex>
# Если <tex>b[j - 1] < a[i] < b[j]</tex>, то <tex>a[i]</tex> и есть <tex>k</tex>-ая порядковая статистика
# Если <tex>a[i - 1] < b[j] < a[i]</tex>, то <tex>b[j]</tex> и есть <tex>k</tex>-ая порядковая статистика
Итак, если одно из двух последних условий выполняется, то мы нашли нужный элемент. Иначе нам нужно сократить область поиска, как задумывалось в начале.
Будем использовать <tex>i</tex> и <tex>j</tex> как опорные точки для разделения массивов. Заметим, что если <tex>a[i] < b[j]</tex>, то <tex>a[i] < b[j - 1]</tex> (иначе второе условие бы выполнялось). В таком случае на месте <tex>i</tex>-го элемента может стоять максимум <tex>i + (j - 2) + 2 = (i + j)</tex>-ый порядковый элемент после слияния массивов (так получится, если <tex>a[i] > b[j - 2]</tex>), а значит элемент с номером <tex>i</tex> и все до него в массиве <tex>A</tex> никогда не будут <tex>k</tex>-ой порядковой статистикой.
