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

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

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

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

1. Начните с отсортированного массива.
2. Определите средний элемент массива.
3. Сравните средний элемент с искомым значением.
4. Если средний элемент равен искомому значению, верните его индекс.
5. Если искомое значение меньше среднего элемента, повторите шаги 2-4 для левой половины массива.
6. Если искомое значение больше среднего элемента, повторите шаги 2-4 для правой половины массива.
7. Если искомое значение не найдено после рассмотрения всех элементов, верните значение, указывающее на отсутствие элемента (обычно -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. Шаг 1:
   1. `left = 0`, `right = 9`
   2. `mid = (0 + 9) / 2 = 4` (индекс 4, значение `16`)
   3. `23 > 16`, значит, ищем в правой половине.
2. Шаг 2:
   1. `left = 5`, `right = 9`
   2. `mid = (5 + 9) / 2 = 7` (индекс 7, значение `56`)
   3. `23 < 56`, значит, ищем в левой половине.
3. Шаг 3:
   1. `left = 5`, `right = 6`
   2. `mid = (5 + 6) / 2 = 5` (индекс 5, значение `23`)
   3. `23 == 23`, элемент найден, возвращаем индекс `5`.

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

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

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

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

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

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

Недостатки:

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

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

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

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

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