No.513
[Full thread]
Задачка: есть массив чисел, отсортированных по возрастанию и интервал чисел, которые нужно в этот массив вставить так, чтобы массив остался отсортированным и числа не повторялись.
Например для массива [1, 2, 3, 4, 6, 10, 12, 13, 14, 15] и интервала 2-12 конечный результат должен быть [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15].
Все это хочется реализовать максимально просто и эффективно, то есть с минимальным использованием памяти, так что код с использованием функциональных языков и списков не интересует. Основная идея в том, чтобы находить "дыру", увеличивать количество памяти на размер дыры, отодвигать все элементы справа от нее на размер дыры, заполнять и двигаться дальше. Но есть два граничных условия: когда дыра до начала массива и когда дыра после конца массива. Хотелось бы как-то избавиться от этих проверок, которые портят няшный сишный код. Какие есть идеи? Пока что придумал только добавить ноль и бесконечность в начало и конец массива, но это все не очень красиво. Может можно придумать что-то с указателями?