Алгоритмы и структуры данных

Бинарный поиск

Алгоритм поиска, используемый для поиска определенного элемента в отсортированном массиве.

Шаг 1: Установите два указателя: один в начале списка и один в конце списка.
Шаг 2: Вычислите среднее положение между левым и правым указателями и сравните элемент в средней позиции с целевым элементом.
- Если элемент в средней позиции соответствует целевому элементу, поиск успешен и возвращается позиция (индекс) целевого элемента.
- Если средний элемент больше целевого элемента, удалите правую половину пространства поиска, переместив правый указатель на одну позицию перед средним.
- Если средний элемент меньше целевого элемента, удалите левую половину пространства поиска, переместив левый указатель на одну позицию после середины.

Сложность: O(log n)

www.tgoop.com/the_algorithms/4575

5.9K viewsOct 16, 2023 at 09:00

Бинарный поиск

Алгоритм поиска, используемый для поиска определенного элемента в отсортированном массиве.

Шаг 1: Установите два указателя: один в начале списка и один в конце списка.
Шаг 2: Вычислите среднее положение между левым и правым указателями и сравните элемент в средней позиции с целевым элементом.
- Если элемент в средней позиции соответствует целевому элементу, поиск успешен и возвращается позиция (индекс) целевого элемента.
- Если средний элемент больше целевого элемента, удалите правую половину пространства поиска, переместив правый указатель на одну позицию перед средним.
- Если средний элемент меньше целевого элемента, удалите левую половину пространства поиска, переместив левый указатель на одну позицию после середины.

Сложность: O(log n)

BY Алгоритмы и структуры данных