Просмотр исходного текста страницы Бинарный поиск

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

== Как это работает ==

Алгоритм бинарного поиска работает следующим образом:

# Начните с отсортированного массива.
# Определите средний элемент массива.
# Сравните средний элемент с искомым значением.
# Если средний элемент равен искомому значению, верните его индекс.
# Если искомое значение меньше среднего элемента, повторите шаги 2-4 для левой половины массива.
# Если искомое значение больше среднего элемента, повторите шаги 2-4 для правой половины массива.
# Если искомое значение не найдено после рассмотрения всех элементов, верните значение, указывающее на отсутствие элемента (обычно -1).

== Псевдокод ==

Вот псевдокод для алгоритма бинарного поиска:

```
function binarySearch(arr, target) {
    left = 0;
    right = arr.length - 1;

    while (left <= right) {
        mid = Math.floor((left + right) / 2);

        if (arr[mid] == target) {
            return mid;  // Элемент найден, вернуть индекс
        }

        if (target < arr[mid]) {
            right = mid - 1;  // Искать в левой половине
        } else {
            left = mid + 1;   // Искать в правой половине
        }
    }

    return -1;  // Элемент не найден
}
```

== Пример ==

Давайте рассмотрим пример поиска числа `23` в отсортированном массиве `[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]`:

# '''Шаг 1:'''
## `left = 0`, `right = 9`
## `mid = (0 + 9) / 2 = 4` (индекс 4, значение `16`)
## `23 > 16`, значит, ищем в правой половине.
# '''Шаг 2:'''
## `left = 5`, `right = 9`
## `mid = (5 + 9) / 2 = 7` (индекс 7, значение `56`)
## `23 < 56`, значит, ищем в левой половине.
# '''Шаг 3:'''
## `left = 5`, `right = 6`
## `mid = (5 + 6) / 2 = 5` (индекс 5, значение `23`)
## `23 == 23`, элемент найден, возвращаем индекс `5`.

== Временная сложность ==

Временная сложность бинарного поиска:

*   '''Лучший случай''': $O(1)$ (элемент найден в середине массива).
*   '''Средний случай''': $O(\log n)$
*   '''Худший случай''': $O(\log n)$

== Преимущества и недостатки ==

=== Преимущества: ===

*   Очень эффективен для поиска в больших отсортированных массивах.
*   Логарифмическая временная сложность.

=== Недостатки: ===

*   Требует, чтобы массив был отсортирован.
*   Не эффективен для часто изменяющихся массивов, так как требует пересортировки после каждой вставки или удаления.

== Когда использовать ==

Бинарный поиск следует использовать, когда:

*   Нужно искать элемент в отсортированном массиве.
*   Производительность поиска важна.

Если массив не отсортирован, необходимо сначала отсортировать его (что может занять $O(n \log n)$ времени) или использовать другой алгоритм поиска, такой как линейный поиск, если массив небольшой.