Двоичный поиск в упорядоченном массиве
Алгоритм на псевдокоде (первая версия)
Алгоритм на псевдокоде (вторая версия)
Трудоемкость двоичного поиска
Трудоемкость двоичного поиска
Графики трудоемкости двоичного поиска
Сортировка данных со сложной структурой
Сортировка данных со сложной структурой
Наполовину пуст? Наполовину полон?
Сортировка по множеству ключей
Индексация данных
Построение индексного массива
Построение индексного массива Алгоритм на псевдокоде (на примере пузырьковой сортировки)
Преимущества индексации
Преимущества индексации
722.21K
Category: programmingprogramming

Двоичный поиск в упорядоченном массиве

1. Двоичный поиск в упорядоченном массиве

ДВОИЧНЫЙ ПОИСК
В УПОРЯДОЧЕННОМ МАССИВЕ
Пусть дан массив А = (a1, a2, … , an ),
упорядоченный по возрастанию, т.е. a1 ≤ a2 ≤ … ≤ an .
Найти: 1) Элемент с ключом Х;
2) Все элементы с ключом Х.

2.

Если массив не упорядочен, то единственный
способ поиска – перебор, трудоемкость О(n).
В случае быстрого двоичного поиска
трудоемкость О(
English     Русский Rules