Иногда хочется решить задачу просто потому что решение легко проверить, прям сразу для множество вариантов. Взяли список из 25 элементов, отсортировали его, и применили искомую функцию 25 раз, профит. Плюс задачка напоминает обложку тетрадки по арифметике за пятый класс, там где табличка произведений, ну та где находим пятый столбец и седьмой ряд и на пересечений их будет произведение. Там же в табличке видно что 6x6 - это квадрат, а 9x4 это совсем не квадрат (скорее ближе к прямоугольнику) хотя площадь у них равная. Так вот, "литкод" хочет чтобы мы нашли n-ый элемент в данной табличке по возрастанию.
Одно из возможных решений - собрать элементы в список, отсортировать его, взять n-ый элемент, профит (на всякий случай не забываем про алгоритм select_nth_unstable в расте). К сожалению, элементов в табличке очень много, поэтому интереснее собрать только часть элементов. Помедитировав немного над табличкой (https://ru.wikipedia.org/wiki/Таблица_умножения) лучше ее разбить на группы (как показано ниже) и только после собрать и выбрать элемент. Критерий группы - все элементы меньше или равны крайнему правому (см. плиз на рисунке ниже).
1 2 3 4 5
2 4 * * *
3 * * * *
4 * * * *
5 * * * *
- - - - -
- - 6 8 10
- 6 9 * *
- 8 * * *
- 10 * * *
- - - - -
- - - - -
- - - 12 15
- - 12 * *
- - 15 * *
- - - - -
- - - - -
- - - - -
- - - 16 20
- - - 20 *
- - - - -
- - - - -
- - - - -
- - - - -
- - - - 25
Принцип разбиения на группы вроде как напоминает https://ru.wikipedia.org/wiki/Гармонический_ряд, что вроде неплохой знак :) Так, теперь само разбиение: первый ряд из таблички берем целиком, от второго ряда первую половину, третьего - первую треть и т.д. Для второй итерации - вторую половину второго ряда, далее вторую треть третьего, вторую четверть и т.д. То есть если табличка 10x10, для третьего ряда разбиение есть 3,3,4 по элементам для первой, второй и третьей итерации; для четвертого ряда 2,3,2,3 - для четырех итераций соответственно. Еще момент, для каждой итерации кол-во элементов в группе различно. Например для таблички из рисунка выше в первой итерации 5+2+1+1+1=10 элементов, для второй итерации 3+2+1+1=7.
Чтобы найти 20-й элемент в табличке 5x5, мы берем третью группу, так как в первой группе 10 элементов, во второй - 7, третьей - 4; то есть мы складываем дельты, пока сумма не превысит искомый индекс. Звучит OK, но работает медленно - потому что дельта разная и, как следствие, линейный поиск.
Для бинарного поиска неплохо бы перейти от дельт 10,7,4,3,1 к полусуммам 10, 17, 21, 24, 25. Каждый ряд таблички участвует в нескольких группах, например третий ряд - в первых трех группах, четвертый - в четырех группах. Для третьго ряда разбиение 1,2,2 по кол-ву элементов, для четвертого 1,1,1,2. Немного детальнее - для таблички 5x5 и третьего ряда мы пять делим на три и остаток от деления переносим на следующий шаг. Чтобы перейти к полусуммам, на каждый шаг деления на три давайте пять умножим на i (номер шага), то есть получим (5/3, 10/3, 15/3 -> 1,3,5 то есть наши полусуммы. Еще раз для сравнения было->стало: (5/3, {5+r}/3, {5+r2}/3) или 1,2,2 -> (5/3, 10/3, 15/3) или 1,3,5. Собираем полусуммы рядов в группу, профит. Остальное - детали реализации.
Наверно, основной поинт статьи в переходе от линейного к бинарному поиску. На всякий случай, для миллиарда элементов binary search делает 30 проверок, linear search примерно 2**30. Спасибо за внимание.
