Алгоритмы двоичного и n-арного поиска.

Полный анализ алгоритма поиска.

Что такое алгоритм двоичного поиска?

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

В этом алгоритме элемент, который необходимо найти, сравнивается со средним элементом отсортированного массива. Процесс поиска индекса элемента повторяется до тех пор, пока элемент не будет найден или пока не будут выполнены все сравнения.

Этот алгоритм можно реализовать двумя способами:

1. Итерационный подход
2. Рекурсивный подход

Рекурсивный подход следует стратегии разделяй и властвуй.

Визуализируете алгоритм двоичного поиска?

Ниже приведены шаги, выполняемые при поиске элемента:

1. Возьмите ввод, который вы хотите найти в данном отсортированном массиве.

Допустим, это элемент x=4.

2. Теперь давайте возьмем два индекса low и high как самый низкий и самый высокий индексы данного массива.

3. Найдите индекс mid, используя младшие и высокие индексы данного отсортированного массива.

средний = (низкий + высокий) / 2 → средний = (0 + 6) / 2 → средний = 3

4. Сравните данный элемент с элементом в середине индекса.

То есть x (i.e. x=4) с array[mid](i.e. 8). Если x равно array [mid], то элемент найден в данном массиве.

5. Если x меньше, чем array [mid], измените индекс high на (mid-1).

6. В противном случае, если x больше, чем array [mid], измените индекс low на (mid + 1).

7. Выполняйте шаги с 3 по 6, пока высокий не станет больше или равен до минимума.

Теперь давайте разработаем алгоритм двоичного поиска:

1. Итерационный подход:

2. Рекурсивный подход:

ВЫХОД:

The Element is found in the array at index 1

Анализ сложности времени и пространства:

Сложность времени:

1. Наилучший случай. Временная сложность наилучшего случая возникает, когда данный элемент находится в середине индекса только на первой итерации. Следовательно, временная сложность будет O(1).
2. Худший случай. В худшем случае временная сложность возникает, когда данный элемент находится в крайнем левом или правом углу данного массива.

В таком случае задача делится на две части:

T(n) = T(n/2) + contant

Решение для вышеуказанного отношения повторяемости - O(log₂(n)).

Космическая сложность:

На). [для хранения элементов массива].

Алгоритм n-арного поиска:

Для поиска n-ary мы должны выполнить следующее:

1. Выполните n-1 проверки границ, чтобы выделить один из n диапазонов.
2. Перейти в диапазон, полученный на предыдущем шаге.

Следовательно, временная сложность по существу равна O((n-1)*logₙ(n)), которая оценивается как O(n)..

Предположим, мы хотим реализовать трехзначный алгоритм поиска, поэтому в этом случае будет два средних элемента и 3 раздела массива. Таким образом, для этой реализации сложность времени будет log₃(n).

Если вам понравилась эта статья, подумайте о следите за мной. В основном я пишу о Java-программировании, структурах данных, алгоритмах, SQL, GIT, Linux, лучших практиках и т. Д.

Ссылка: Введение в алгоритмы.