Двоичный поиск в упорядоченном массиве
Алгоритм на псевдокоде (первая версия)
Алгоритм на псевдокоде (вторая версия)
Трудоемкость двоичного поиска
Трудоемкость двоичного поиска
Графики трудоемкости двоичного поиска
Сортировка данных со сложной структурой
Сортировка данных со сложной структурой
Наполовину пуст? Наполовину полон?
Сортировка по множеству ключей
Индексация данных
Построение индексного массива
Построение индексного массива Алгоритм на псевдокоде (на примере пузырьковой сортировки)
Преимущества индексации
Преимущества индексации
722.21K
Категория: ПрограммированиеПрограммирование
Похожие презентации:
Основы программирования. Простые алгоритмы поиска и сортировки
Основы программирования. Простые алгоритмы поиска и сортировки
Массивы. Поиск элемента в массиве
Массивы. Поиск элемента в массиве
Двоичные деревья
Двоичные деревья
Поиск в информационном массиве. Тема 4
Поиск в информационном массиве. Тема 4
Сортировки. Двоичный поиск
Сортировки. Двоичный поиск
Алгоритмы сортировки массивов
Алгоритмы сортировки массивов
Одномерные массивы. Алгоритмы обработки массивов. Сортировка. Лекции 7-9 по алгоритмизации и программированию
Одномерные массивы. Алгоритмы обработки массивов. Сортировка. Лекции 7-9 по алгоритмизации и программированию
Алгоритмы поиска. Лекция 4
Алгоритмы поиска. Лекция 4
Массивы. (Тема 6)
Массивы. (Тема 6)
Рекурсия, быстрая сортировка, двоичный поиск
Рекурсия, быстрая сортировка, двоичный поиск

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

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

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

2.

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