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

Бинарный поиск — это алгоритм поиска, в котором мы делим заданный набор элементов посередине и сравниваем искомый элемент с элементом посередине. Если элемент меньше среднего, мы повторяем процесс в первой половине набора данных, иначе во второй половине, пока искомый элемент не будет равен среднему элементу.

Алгоритм

Давайте рассмотрим алгоритм и поймем, как реализовать бинарный поиск.

int low = 0;
int high = arr.length - 1;

while (low <= high) {
    int mid = low + (high - low) / 2;

    if (key == arr[mid]) {
        return mid;
    } else if (key > arr[mid]) {
        low = mid + 1;
    } else {
        high = mid - 1;
    }
}

return -1;

В приведенном выше фрагменте кода мы берем два индекса: low для начала массива и high для последнего элемента в массиве.
Выполнение цикла по массиву до тех пор, пока low не станет меньше или равен индексу high, мы вычисляем индекс mid на каждой итерации.
Учитывая элемент для поиска обозначается переменной key,
Если key равен элементу в среднем индексе массива, мы возвращаем mid.
Если ключ больше, чем элемент в среднем индексе массива, мы устанавливаем нижний индекс равным mid+1 element.
Если ключ меньше, чем элемент в среднем индексе массива, мы устанавливаем высокий индекс на элемент mid-1.
Если ключ не найден в массиве, мы возвращаем -1;

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

Бинарный поиск следует методу разделяй и властвуй.

Временная сложность: O(logn)
Всякий раз, когда мы сталкиваемся с алгоритмом, который следует методу "разделяй и властвуй", т. е. делит массив пополам на каждой итерации, временная сложность будет равна логарифмический.

Пространственная сложность:O(1)
Двоичный поиск при итеративной реализации не использует дополнительное пространство и, следовательно, занимает постоянное пространство на протяжении всего своего выполнения.

Использование и преимущества

Он сужает набор данных поиска.
Его можно использовать для эффективного поиска элемента/объекта в огромном наборе данных.
Его можно использовать в других алгоритмах для упрощения конечной цели алгоритма.

Вы дошли до конца статьи и готовы реализовать или использовать двоичный поиск в реальных решениях.

Увидимся в следующей статье, а пока hasta luego.