Массивы, двоичный поиск и O-нотация

живой пример

public class BinarySearchDemo {
    static int steps = 0;

    static int binarySearch(int[] a, int key) {
        int lower = 0;
        int upper = a.length - 1;
        while (lower <= upper) {
            steps++;
            int mid = (lower + upper) >>> 1;
            if (a[mid] == key) return mid;
            if (a[mid] < key) lower = mid + 1;
            else upper = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] a = {3, 7, 11, 18, 23, 29, 34, 41, 52, 63, 70};
        int found = binarySearch(a, 63);
        System.out.println("63 лежит в ячейке " + found);
        System.out.println("сравнений: " + steps + ", ячеек в массиве: " + a.length);
    }
}

живой пример

package main

import "fmt"

var steps = 0

func binarySearch(a []int, key int) int {
	lower, upper := 0, len(a)-1
	for lower <= upper {
		steps++
		mid := int(uint(lower+upper) >> 1)
		switch {
		case a[mid] == key:
			return mid
		case a[mid] < key:
			lower = mid + 1
		default:
			upper = mid - 1
		}
	}
	return -1
}

func main() {
	a := []int{3, 7, 11, 18, 23, 29, 34, 41, 52, 63, 70}
	found := binarySearch(a, 63)
	fmt.Println("63 лежит в ячейке", found)
	fmt.Printf("сравнений: %d, ячеек в массиве: %d\n", steps, len(a))
}

живой пример

let steps = 0;

function binarySearch(a, key) {
  let lower = 0;
  let upper = a.length - 1;
  while (lower <= upper) {
    steps++;
    const mid = (lower + upper) >>> 1;
    if (a[mid] === key) return mid;
    if (a[mid] < key) lower = mid + 1;
    else upper = mid - 1;
  }
  return -1;
}

const a = [3, 7, 11, 18, 23, 29, 34, 41, 52, 63, 70];
const found = binarySearch(a, 63);
console.log(`63 лежит в ячейке ${found}`);
console.log(`сравнений: ${steps}, ячеек в массиве: ${a.length}`);

живой пример

steps = 0


def binary_search(a: list[int], key: int) -> int:
    global steps
    lower, upper = 0, len(a) - 1
    while lower <= upper:
        steps += 1
        mid = (lower + upper) // 2
        if a[mid] == key:
            return mid
        if a[mid] < key:
            lower = mid + 1
        else:
            upper = mid - 1
    return -1


a = [3, 7, 11, 18, 23, 29, 34, 41, 52, 63, 70]
found = binary_search(a, 63)
print(f"63 лежит в ячейке {found}")
print(f"сравнений: {steps}, ячеек в массиве: {len(a)}")

Свой массив с ручным ростом писать почти никогда не нужно — всё это давно обкатано в стандартной библиотеке. Но выбирать структуру всё равно приходится, а для этого надо знать, что у неё внутри.

Эталонная реализация массива в Java — ArrayList. Слово «list» в названии сбивает с толку: никаких узлов и ссылок внутри нет, это самый обычный массив объектов, который класс держит в поле и подменяет на больший, когда места перестаёт хватать.

Рост устроен так: когда массив заполнен, ArrayList заводит новый — примерно в полтора раза длиннее — и переписывает туда старые элементы. Такое копирование стоит O(N), но случается тем реже, чем список длиннее. Если размазать эту цену по всем добавлениям, каждое add в конец обходится в O(1) амортизированно: почти всегда один шаг, изредка — дорогой переезд.

Переездов можно избежать, если размер известен заранее: new ArrayList<>(100_000) выделяет массив нужной длины сразу, а ensureCapacity(n) делает то же для уже существующего списка перед массовым добавлением. На сотне тысяч элементов это экономит полтора десятка копирований; в хеш-таблице тот же приём, задать ёмкость заранее, разобран в своей статье и там он важнее, потому что перестройка дороже.

Вторая цена ArrayList, о которой молчит слово «массив», это упаковка. Хранить в нём можно только объекты, поэтому ArrayList<Integer> держит не числа, а ссылки на объекты Integer: четыре байта ссылки плюс шестнадцать байт объекта против четырёх байт в int[], в пять раз больше памяти, и обход прыгает по объектам вместо чтения подряд. Для чисел в горячем коде берут int[] или long[], а ArrayList<Integer> там, где важнее удобство.

Остальная сложность — ровно как у массива из статьи:

• get(i) и set(i, v) — O(1), адрес ячейки считается по индексу;
• add(v) в конец — O(1) амортизированно;
• add(i, v) и remove(i) в середину — O(N): соседей приходится сдвигать. Делает это System.arraycopy — быстрая операция копирования памяти, но работы всё равно линейно;
• contains и indexOf — O(N), это тот самый линейный поиск.

Двоичный поиск руками тоже писать не надо: для отсортированного массива есть Arrays.binarySearch, для отсортированного списка — Collections.binarySearch. Внутри у них тот же цикл с делением диапазона пополам, включая безопасный сдвиг >>> вместо деления на два.

Грабля здесь одна, зато злая: binarySearch не проверяет, отсортированы ли данные. На неупорядоченном массиве он не упадёт и никак не пожалуется — просто вернёт неверный ответ. И возвращаемое значение надо читать внимательно: когда элемент не найден, метод отдаёт не -1, а отрицательное число, в котором закодирована позиция для вставки — -(позиция) - 1. Все три случая сразу:

Вторая грабля живёт в самом ArrayList<Integer>, и попадаются на неё все. У списка два метода remove: remove(int index) удаляет по номеру, remove(Object o) по значению. Для List<Integer> вызов list.remove(1) выбирает первый, потому что литерал 1 это int, и удаляет элемент с индексом 1, а не число 1. Чтобы удалить значение, его упаковывают явно: list.remove(Integer.valueOf(1)). Ошибка тихая: список стал короче, исключения нет, просто пропало не то.

живой пример

import java.util.Arrays;

public class JdkBinarySearch {
    public static void main(String[] args) {
        int[] sorted = {3, 7, 11, 18, 23};
        System.out.println("11 -> " + Arrays.binarySearch(sorted, 11));
        System.out.println("12 -> " + Arrays.binarySearch(sorted, 12));

        int[] unsorted = {23, 3, 18, 7, 11};
        System.out.println("11 в неотсортированном -> " + Arrays.binarySearch(unsorted, 11));
    }
}

Первая строка — честная находка в ячейке 2. Вторая: числа 12 нет, а -4 читается как «вставлять надо в позицию 3». Третья — ловушка: 11 в массиве есть, но массив не отсортирован, и метод молча отвечает «не нашёл». Отвечает по тому же правилу: -1 здесь — это -(0) - 1, то есть «вставлять надо в позицию 0». Просто на этот раз совет бесполезен, потому что данные не отсортированы.

Свой массив с ручным ростом в Go писать не нужно: он встроен в язык и называется срезом. Слово «срез» намекает на устройство: []int это не сами данные, а маленькая структура из трёх полей: указатель на настоящий массив, длина len и ёмкость cap, то есть сколько ячеек выделено за спиной.

Рост устроен так: append пишет в свободную ячейку, пока len меньше cap. Когда ячейки кончились, среда выполнения выделяет новый массив, до 256 элементов вдвое больше, дальше примерно в 1,25 раза, и копирует туда старые элементы. Копирование стоит O(N), но случается тем реже, чем срез длиннее, поэтому append в конец обходится в O(1) амортизированно.

Из этого устройства растёт главная грабля срезов: после переезда старый и новый срез смотрят на разные массивы. Функция, которая делает s = append(s, x) со своей копией среза, может изменить массив вызывающего, а может и не изменить, смотря хватило ли ёмкости. Поэтому результат append всегда присваивают обратно, а срез, который отдают наружу, при необходимости копируют через slices.Clone.

Переездов можно избежать, если размер известен заранее: make([]int, 0, 100_000) выделяет массив нужной ёмкости сразу. На сотне тысяч элементов это экономит два десятка копирований и заметно снижает нагрузку на сборщик мусора.

Второй платы, упаковки, у срезов чисел нет: []int хранит сами числа подряд, по восемь байт на элемент, и обход читает память последовательно. Расплата появляется у []any и у среза указателей: там лежат ссылки, а значения разбросаны по куче. Для чисел в горячем коде берут срез конкретного типа, а []any только там, где без него никак.

Остальная сложность — ровно как у массива из статьи:

• s[i] чтение и запись — O(1), адрес ячейки считается по индексу;
• append(s, v) в конец — O(1) амортизированно;
• slices.Insert(s, i, v) и slices.Delete(s, i, i+1) в середину — O(N): соседей сдвигает copy, быстрая операция копирования памяти, но работы всё равно линейно;
• slices.Contains и slices.Index — O(N), это тот самый линейный поиск.

Двоичный поиск руками тоже писать не надо: в пакете slices есть BinarySearch, а в sort старый SearchInts и универсальный sort.Search по любому условию. Внутри у них тот же цикл с делением диапазона пополам, только середина считается через беззнаковое uint(i+j) >> 1.

Грабля здесь одна, зато злая: BinarySearch не проверяет, отсортированы ли данные. На неупорядоченном срезе он не упадёт и никак не пожалуется, просто вернёт неверный ответ. И возвращаемое значение читают внимательно: функция отдаёт два значения, позицию и признак found. Когда элемента нет, позиция это место, куда его надо вставить, чтобы порядок сохранился, а не -1. У sort.SearchInts признака нет вовсе: он всегда возвращает точку вставки, и «нашёл или нет» проверяют сами по i < len(s) && s[i] == x. Все три случая сразу:

живой пример

package main

import (
	"fmt"
	"slices"
)

func main() {
	sorted := []int{3, 7, 11, 18, 23}
	i, found := slices.BinarySearch(sorted, 11)
	fmt.Println("11 ->", i, found)
	i, found = slices.BinarySearch(sorted, 12)
	fmt.Println("12 ->", i, found)

	unsorted := []int{23, 3, 18, 7, 11}
	i, found = slices.BinarySearch(unsorted, 11)
	fmt.Println("11 в неотсортированном ->", i, found)
}

Первая строка — честная находка: позиция 2 и found равен true. Вторая: числа 12 нет, found равен false, а позиция 3 это место для вставки. Третья — ловушка: 11 в срезе есть, но срез не отсортирован, и функция молча отвечает «нет, вставлять в позицию 2». Ошибки никакой, просто ответ неверный, потому что данные не отсортированы.

Свой массив с ручным ростом в JavaScript писать не нужно: Array уже динамический. Под капотом движок V8 держит для массива непрерывное хранилище с запасом и следит, что именно в нём лежит: массив из одних небольших целых хранится плотно, как настоящий массив чисел; стоит положить в него дробь, строку или объект, и представление меняется на более общее и медленное. Дырки (delete a[3], запись далеко за конец) переводят массив в «разреженный» режим, где доступ по индексу уже не один шаг.

Рост устроен так: push пишет в свободную ячейку, а когда запас кончился, V8 выделяет хранилище примерно в полтора раза больше и переписывает элементы. Копирование стоит O(N), но случается тем реже, чем массив длиннее, поэтому push в конец обходится в O(1) амортизированно.

Задать размер заранее можно через new Array(n), но это создаёт как раз дырявый массив, и выигрыш легко потерять. Для больших массивов чисел берут типизированные массивы: new Int32Array(100_000) выделяет ровно 400 килобайт подряд, без упаковки и без переездов, только размер у него фиксированный.

Вторая цена обычного Array, о которой молчит название, это упаковка. В общем режиме массив хранит не числа, а ссылки на объекты в куче, и обход прыгает по памяти вместо чтения подряд. Пока в массиве только целые, V8 обходится без этого; типизированный массив гарантирует плотность всегда.

Остальная сложность — ровно как у массива из статьи:

• a[i] чтение и запись — O(1) в плотном массиве;
• push(v) в конец — O(1) амортизированно;
• splice(i, 0, v) и splice(i, 1) в середину — O(N): соседей приходится сдвигать; shift и unshift с начала стоят столько же;
• includes и indexOf — O(N), это тот самый линейный поиск.

Двоичного поиска в стандартной библиотеке JavaScript нет: indexOf идёт перебором и не знает, что массив отсортирован. Функцию пишут руками, десять строк, или берут пакет вроде binary-search.

Грабля у самодельного поиска та же, что у библиотечного в других языках: он не проверяет, отсортированы ли данные. На неупорядоченном массиве он не упадёт и никак не пожалуется, просто вернёт неверный ответ. Все случаи сразу:

живой пример

function binarySearch(a, key) {
  let lower = 0;
  let upper = a.length - 1;
  while (lower <= upper) {
    const mid = (lower + upper) >>> 1;
    if (a[mid] === key) return mid;
    if (a[mid] < key) lower = mid + 1;
    else upper = mid - 1;
  }
  return -1;
}

const sorted = [3, 7, 11, 18, 23];
console.log("11 ->", binarySearch(sorted, 11));
console.log("12 ->", binarySearch(sorted, 12));
console.log("11 через indexOf ->", sorted.indexOf(11), "(перебор, а не деление пополам)");

const unsorted = [23, 3, 18, 7, 11];
console.log("11 в неотсортированном ->", binarySearch(unsorted, 11));

Первая строка — честная находка в ячейке 2. Вторая: числа 12 нет, ответ -1. Третья показывает, что indexOf находит то же самое, только за N шагов вместо трёх. Четвёртая — ловушка: 11 в массиве есть, но массив не отсортирован, и функция молча отвечает «не нашёл».

Свой массив с ручным ростом в Python писать не нужно: он и есть list. Слово «список» сбивает с толку: никаких узлов и ссылок на следующий элемент внутри нет, это обычный массив указателей на объекты, который интерпретатор держит в памяти подряд и подменяет на больший, когда места перестаёт хватать.

Рост устроен так: когда массив заполнен, list выделяет новый с запасом примерно в одну восьмую сверх нужного и переписывает туда старые указатели. Запас скромный, поэтому переезды случаются чаще, чем при росте вдвое, но каждый дешевле. Копирование стоит O(N), но случается тем реже, чем список длиннее, и append в конец обходится в O(1) амортизированно.

Переездов можно избежать, если размер известен заранее: [0] * 100_000 выделяет список нужной длины сразу, а [None] * n заводит пустые ячейки под заполнение по индексу. Метода «зарезервировать ёмкость» у списка нет.

Вторая цена list, о которой молчит слово «массив», это упаковка, и в Python она обязательна: список хранит не числа, а ссылки на объекты int, по 28 байт на каждое небольшое число плюс 8 байт указателя. Для числовых данных в горячем коде берут array('i') из стандартной библиотеки или массивы NumPy: там числа лежат подряд по четыре или восемь байт, и обход в разы быстрее.

Остальная сложность — ровно как у массива из статьи:

• a[i] чтение и запись — O(1), адрес ячейки считается по индексу;
• append(v) в конец — O(1) амортизированно;
• insert(i, v), pop(i) и del a[i] в середину — O(N): соседей приходится сдвигать; pop(0) с начала стоит столько же, для очереди берут deque;
• in и index — O(N), это тот самый линейный поиск.

Двоичный поиск руками тоже писать не надо: модуль bisect даёт bisect_left и bisect_right для отсортированного списка. Внутри тот же цикл с делением диапазона пополам, а переполнения индексов в Python не бывает: целые растут, сколько нужно.

Грабля здесь одна, зато злая: bisect не проверяет, отсортированы ли данные. На неупорядоченном списке он не упадёт и никак не пожалуется, просто вернёт неверный ответ. И возвращаемое значение надо читать внимательно: bisect_left возвращает не «нашёл или нет», а позицию, куда элемент надо вставить, чтобы порядок сохранился. Нашёлся ли он, проверяют сами: i < len(a) and a[i] == x. Все три случая сразу:

живой пример

from bisect import bisect_left


def index_of(a: list[int], key: int) -> int:
    i = bisect_left(a, key)
    return i if i < len(a) and a[i] == key else -1


sorted_values = [3, 7, 11, 18, 23]
print("11 ->", index_of(sorted_values, 11))
print("12 ->", index_of(sorted_values, 12), "(bisect_left предлагает позицию", bisect_left(sorted_values, 12), ")")

unsorted = [23, 3, 18, 7, 11]
print("11 в неотсортированном ->", index_of(unsorted, 11))

Первая строка — честная находка в ячейке 2. Вторая: числа 12 нет, index_of отвечает -1, а сам bisect_left подсказывает, что вставлять надо в позицию 3. Третья — ловушка: 11 в списке есть, но список не отсортирован, и поиск молча отвечает «не нашёл».

Вторая грабля живёт в удалении, и на неё попадаются пришедшие из Java: a.remove(1) удаляет значение 1, первое встреченное, а не ячейку с индексом 1; по индексу удаляют через del a[1] или a.pop(1). Ошибка тихая: список стал короче, исключения нет, просто пропало не то.

• В Java массив из статьи — это ArrayList: get/set за O(1), add в конец за O(1) амортизированно (рост примерно в полтора раза), вставка и удаление в середину за O(N).
• Arrays.binarySearch не проверяет сортировку и на неупорядоченных данных молча врёт; «не нашёл» он возвращает как -(позиция вставки) - 1, а не как -1.
• Размер известен заранее — задайте его в конструкторе или через ensureCapacity; ArrayList<Integer> хранит ссылки на объекты и стоит впятеро больше int[].
• У List<Integer> remove(1) удаляет по индексу, а не значение 1: для значения пишут remove(Integer.valueOf(1)).

• В Go массив из статьи — это срез: s[i] за O(1), append в конец за O(1) амортизированно (рост вдвое, после 256 элементов примерно в 1,25 раза), slices.Insert и slices.Delete в середину за O(N).
• slices.BinarySearch не проверяет сортировку и на неупорядоченных данных молча врёт; возвращает позицию и признак found, «не нашёл» это позиция для вставки, а не -1.
• Размер известен заранее — задайте ёмкость в make([]T, 0, n); результат append всегда присваивают обратно, иначе после переезда данные разъедутся.

• В JavaScript массив из статьи — это Array: a[i] за O(1), push за O(1) амортизированно (рост примерно в полтора раза), splice в середину и shift с начала за O(N).
• Двоичного поиска в стандартной библиотеке нет, indexOf идёт перебором; самодельный поиск сортировку не проверяет и на неупорядоченных данных молча врёт.
• Плотный массив чисел быстрее общего: дырки и смешанные типы переводят его в медленный режим; для больших числовых данных берут Int32Array или Float64Array.

• В Python массив из статьи — это list: a[i] за O(1), append за O(1) амортизированно (запас около одной восьмой), insert и pop(i) в середину за O(N), pop(0) тоже O(N).
• bisect не проверяет сортировку и на неупорядоченных данных молча врёт; возвращает позицию для вставки, а не «нашёл или нет», проверку a[i] == x пишут сами.
• list хранит ссылки на объекты int по 28 байт; для числовых данных берут array или NumPy. a.remove(1) удаляет значение 1, а не ячейку 1; по индексу — del a[1].