Какая алгоритмическая сложность решения задачи поиска первого плохого расчета в массиве из миллиона элементов
Что проверяют
Замечаете ли вы скрытое условие задачи. Ответ «O(n)» верен для произвольного массива, но интервьюер ждёт вопроса: если после первого плохого расчёта все следующие тоже плохие, задача решается за O(log n). Следом просят написать бинарный поиск без ошибки на границах.
Как отвечать
Сначала выясните свойство данных:
- произвольный массив: плохие расчёты разбросаны как угодно. Остаётся линейный проход, O(n), в худшем случае миллион проверок. Быстрее нельзя, любой непроверенный элемент может оказаться первым плохим;
- монотонный массив: до некоторой позиции всё хорошо, после неё всё плохо, например ошибка появилась с определённой даты и тянется дальше. Тогда подходит бинарный поиск по условию «расчёт плохой», O(log n). Для миллиона элементов это 20 проверок, потому что 2²⁰ = 1 048 576.
Каркас на встроенном языке для поиска левой границы: Лево = 0; Право = Массив.ВГраница();, цикл Пока Лево < Право, внутри Середина = Цел((Лево + Право) / 2). Если расчёт в позиции Середина плохой, Право = Середина, иначе Лево = Середина + 1. После цикла проверьте элемент Лево: если и он хороший, плохих нет вовсе.
Разница особенно заметна, когда проверка дорогая, например перепроведение документа или пересчёт регистра. Двадцать таких операций занимают секунды, миллион уже часы.
Практический момент для 1С: если расчёты лежат в базе, перебирать миллион строк в цикле хуже, чем выбрать первую плохую строку запросом ВЫБРАТЬ ПЕРВЫЕ 1 с отбором и сортировкой по порядку. Метод Массив.Найти() тоже линейный и быстрее задачу не решает.
Где спотыкаются
Применяют бинарный поиск к данным без монотонности. Алгоритм вернёт какой-то индекс, но не первый плохой, и на тестах это легко не заметить.
Находят любой плохой элемент, а потом идут влево линейно в поисках первого. В худшем случае это снова O(n), хотя поиск левой границы сразу даёт ответ.
Путают «отсортирован» и «монотонен по условию». Сортировать массив ради поиска нельзя: это O(n log n), и сортировка уничтожает исходный порядок, а вопрос именно про первый по порядку.