У отсортированного массива главное свойство такое:
порядок элементов уже несёт информацию.
Например:
nums = [1, 2, 3, 4, 6, 8]
Это значит:
nums[i] <= nums[i + 1]
для каждого i.
Из этого вытекают мощные штуки.
1. Можно отбрасывать части массива
Если массив отсортирован и ты ищешь 5, а в середине стоит 6, то всё справа от 6 уже тоже не меньше 6.
Значит, 5 там быть не может.
Это основа binary search.
2. Суммы предсказуемо меняются
Для задачи с двумя указателями:
nums = [1, 2, 3, 4, 6, 8]
target = 10
Если:
nums[left] + nums[right] < target
значит сумма слишком маленькая.
Так как справа уже стоит большой элемент, двигать right влево бессмысленно для увеличения суммы.
Нужно двигать left вправо:
1 + 8 = 9
2 + 8 = 10
А если сумма слишком большая — двигаем right влево.
3. Дубликаты стоят рядом
Например:
[1, 1, 1, 2, 2, 3, 4, 4]
Поэтому легко:
удалять дубликаты
считать частоты
пропускать одинаковые элементы
4. Минимум и максимум известны сразу
В возрастающем массиве:
nums[0] # минимум
nums[-1] # максимум
Это часто помогает сразу понять границы задачи.
5. Любой подмассив тоже отсортирован
Если взять кусок:
[1, 2, 3, 4, 6, 8]
[3, 4, 6]
Он тоже отсортирован.
Поэтому можно сужать диапазон и не терять свойство порядка.
6. Можно искать границы
Например:
[1, 2, 2, 2, 3, 4]
Можно найти:
первую позицию 2
последнюю позицию 2
первый элемент >= x
первый элемент > x
Это тоже делается бинарным поиском.
Главная мысль:
в обычном массиве ты почти ничего не знаешь о следующем элементе.
В отсортированном массиве каждый шаг вправо не уменьшает значение.
И именно это позволяет заменять тупой перебор на управляемое движение.
