2.2.3 — что сортировка (2.2.1, 2.2.2) покупает нам за O(n log n) или O(n + k)2.2.3 — what sorting (2.2.1, 2.2.2) buys us for O(n log n) or O(n + k)
Отсортированность — это не просто "красивый порядок": это структура, которую можно использовать, чтобы находить элементы за O(log n) вместо O(n). Здесь: бинарный поиск и его варианты (lower_bound/upper_bound), поиск в повёрнутом отсортированном массиве, тернарный поиск для унимодальных функций, экспоненциальный поиск для неограниченных или почти неограниченных диапазонов.Sortedness isn't just "nice ordering" — it's structure that can be exploited to find elements in O(log n) instead of O(n). Here: binary search and its variants (lower_bound/upper_bound), searching a rotated sorted array, ternary search for unimodal functions, and exponential search for unbounded or near-unbounded ranges.
Все четыре алгоритма этой страницы — вариации одной идеи: поддерживать диапазон [lo, hi), про который известно некоторое свойство (ответ внутри него; функция ещё растёт/уже убывает; элемент, если он есть, лежит здесь), и на каждом шаге отбрасывать половину или треть диапазона, не теряя гарантии. Отличаются они тем, какое именно свойство поддерживается: строгий порядок для бинарного поиска, "порядок с одним изломом" для повёрнутого массива, унимодальность для тернарного поиска, неизвестная заранее граница для экспоненциального поиска.All four algorithms on this page are variations on one idea: maintain a range [lo, hi) about which some property is known (the answer lies inside it; the function is still increasing/already decreasing; the element, if present, lies here), and at each step discard half or a third of the range without losing that guarantee. What differs is which property is maintained: strict order for binary search, "order with one break" for a rotated array, unimodality for ternary search, an unknown-in-advance bound for exponential search.
O(log n) — это не магия, а прямое следствие того, что каждый шаг умножает оставшийся диапазон на константу < 1O(log n) isn't magic — it's a direct consequence of each step multiplying the remaining range by a constant < 1
Порядок в карточках — это и порядок роста сложности условия: от строго отсортированного массива до произвольной унимодальной функции без известных границ. Полный разбор с диаграммами, кодом и живой демонстрацией — на отдельной странице по ссылке в названии.The card order also tracks increasing condition complexity: from a strictly sorted array to an arbitrary unimodal function with unknown bounds. The full writeup with diagrams, code, and a live demo is on its own page via the name link.
Первые четыре — это O(log n) или близко к тому, но не взаимозаменяемы: бинарный поиск ломается на повёрнутом массиве, тернарный поиск не имеет смысла для функции с несколькими локальными экстремумами, а экспоненциальный поиск нужен именно тогда, когда n не только велико, но и заранее неизвестно (например, поиск по бесконечному потоку или указателю без явного размера). Последние четыре карточки (2.2.3.5–2.2.3.8, пока без ссылок) расширяют тот же принцип дальше: jump search и Fibonacci search — альтернативные схемы деления диапазона с иными компромиссами по стоимости шага; interpolation search выходит за пределы чистой модели сравнения, используя сами значения для оценки позиции; saddleback search — не одномерная задача вовсе, а поиск в структуре, отсортированной сразу по двум измерениям.The first four are O(log n) or close to it, but they aren't interchangeable: binary search breaks on a rotated array, ternary search is meaningless for a function with multiple local extrema, and exponential search is needed precisely when n is not just large but unknown in advance (e.g. searching an infinite stream or a pointer without an explicit size). The last four cards (2.2.3.5–2.2.3.8, not yet linked) extend the same principle further: jump search and Fibonacci search are alternative range-splitting schemes with different step-cost trade-offs; interpolation search steps outside the pure comparison model by using the values themselves to estimate position; saddleback search isn't a 1D problem at all, but a search over a structure sorted along two dimensions at once.
Стандартные библиотеки C++ и аналоги в других языках предоставляют бинарный поиск границ диапазона как встроенную операцию — это не учебный пример, а рабочий инструмент для "первый элемент ≥ x" или "диапазон элементов, равных x" на отсортированной структуре.C++'s standard library and equivalents in other languages expose binary search for range boundaries as a built-in operation — not a textbook exercise, but a working tool for "first element ≥ x" or "the range of elements equal to x" on a sorted structure.
git bisect — это бинарный поиск по истории коммитов, где "отсортированность" — это монотонность свойства "сломано" (до какого-то коммита всё было хорошо, после — плохо, и это не меняется туда-обратно) вместо числового порядка.git bisect is binary search over commit history, where "sortedness" is the monotonicity of "broken" (good up to some commit, bad after, without flipping back and forth) rather than numeric order.
Кольцевой буфер логов, где старая часть физически хранится после новой (указатель записи "обернулся"), — это ровно повёрнутый отсортированный массив по временной метке; поиск события по времени использует ту же логику, что и leetcode-задача про "Search in Rotated Sorted Array".A ring-buffer log where the old portion is physically stored after the new one (the write pointer has "wrapped") is exactly a rotated array sorted by timestamp; searching for an event by time uses the same logic as the "Search in Rotated Sorted Array" problem.
Если метрика (например, конверсия в зависимости от цены) унимодальна — растёт до оптимума и падает после, — тернарный поиск находит этот оптимум за O(log n) экспериментов вместо полного перебора значений параметра.If a metric (e.g. conversion as a function of price) is unimodal — rising to an optimum and falling after — ternary search finds that optimum in O(log n) experiments instead of a full sweep over the parameter's values.
Поиск в отсортированном, но не имеющем известной длины источнике (бесконечный поток, файл, размер которого дорого узнавать заранее) начинается с удвоения границы, пока она не "перепрыгнет" искомое значение — именно так реализован std::search в некоторых потоковых интерфейсах и алгоритм поиска в несбалансированных деревьях без явного размера.Searching a sorted but length-unknown source (an infinite stream, a file whose size is expensive to determine upfront) starts by doubling a bound until it overshoots the target value — this is how some streaming search interfaces and searches over size-less unbalanced trees are implemented.
Классическая ошибка в языках с фиксированной шириной целых: lo + hi может переполнить int ещё до деления, даже если сам ответ помещается в диапазон. Правильная форма — mid = lo + (hi - lo) / 2, которая никогда не складывает два больших числа напрямую.A classic bug in fixed-width-integer languages: lo + hi can overflow an int before the division even happens, even though the answer itself fits in range. The correct form is mid = lo + (hi - lo) / 2, which never adds two large numbers directly.
Разница между "первый элемент ≥ x" и "первый элемент > x" — это разница в одном строгом/нестрогом сравнении внутри цикла, но перепутанная граница даёт код, который компилируется, проходит часть тестов и молча ошибается ровно на повторяющихся значениях.The difference between "first element ≥ x" and "first element > x" is a single strict/non-strict comparison inside the loop, but swapping it produces code that compiles, passes some tests, and silently misbehaves exactly on duplicate values.
Поиск в повёрнутом массиве работает, потому что там ровно один излом порядка; если массив повёрнут несколько раз или частично перемешан, определить "какая половина отсортирована" за O(1) уже нельзя — гарантия O(log n) держится только на том конкретном инварианте, который есть у задачи, а не на любом "почти отсортированном" входе.Rotated-array search works because there's exactly one order break; if the array is rotated multiple times or partially shuffled, determining "which half is sorted" in O(1) is no longer possible — the O(log n) guarantee only holds for the specific invariant the problem actually has, not for any "almost sorted" input.