сиаод 2 лаба

Только с отсортированными последовательностями:

1) Бинарный поиск: сравниваем искомый элемент с серединным и если он меньше, отбрасываем вторую половину массива, иначе первую

2) Бинарное дерево:

Формирует дерево по принципам бинарного поиска (слева значения меньше узла, справа значения больше узла)

Красно-чёрное дерево – Бинарное дерево, которое самобалансируется

3) Фибоначчиев: сравнение искомого элемента с элементами, индекс которых формируется на основе ряда Фибоначчи {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …}

Чаще используется для больших последовательностей, не влезающих целиком в память

4) Интерполяционный поиск:

I – первый индекс Ki – минимальный эл

J – последний индекс Kj – максимальный эл

K – искомый

Если элемент от d < искомого, сдвигаем i до него, если >, сдвигаем j

Хэширование

Преобразуем значения с помощью хэш-функции и исходя из результатов вписываем их идентификатор в таблицу.

Коллизия происходит, когда получаем одинаковый хэш и пытаемся записать разные идентификаторы в одну и ту же ячейку.

1) Рехэширование

2)Метод цепочек