Основы программирования на С++ для начинающих

Двоичный (бинарный) поиск С++

Мы с вами уже разобрались с алгоритмом линейного поиска. В той же статье упоминалось, что это не единственный алгоритм, который дает возможность найти заданное значение в массиве. Существуют другие алгоритмы поиска. Двоичный (бинарный) поиск является более эффективным (проверяется асимптотическим анализом алгоритмов) решением в случае, если массив заранее отсортирован.

Предположим, что массив из 12-ти элементов отсортирован по возрастанию:

бинарный поиск с++, двоичный поиск c++, алгоритм

Пользователь задает искомое значение (ключ поиска). Допустим 4. На первой итерации массив делится на две части (ищем средний элемент – midd): (0 + 11) / 2 = 5 (0.5 отбрасываются). Сначала, проверяется значение среднего элемента массива. Если оно совпадает с ключом – алгоритм прекратит работу и программа выведет сообщение, что значение найдено. В нашем случае, ключ не совпадает со значением среднего элемента.

бинарный поиск с++, двоичный поиск c++, алгоритм

Если ключ меньше значения среднего элемента, алгоритм не будет проводить поиск в той половине массива, которая содержит значения больше ключа (т.е. от среднего элемента до конца массива). Правая граница поиска сместится (midd – 1). Далее снова деление массива на 2.

бинарный поиск с++, двоичный поиск c++, алгоритм

Ключ снова не равен среднему элементу. Он больше него. Теперь левая граница поиска сместится (midd + 1).

бинарный поиск с++, двоичный поиск c++, алгоритм

На третьей итерации средний элемент – это ячейка с индексом 3: (3 + 4) / 2 = 3. Он равен ключу. Алгоритм завершает работу.

Пример:

Результат:

бинарный поиск с++, двоичный поиск c++, алгоритм

Двоичный поиск является эффективным алгоритмом — его оценка сложности O(log2(n)), в то время как у обычного последовательного поиска O(n). Это значит, что например, для массива из 1024 элементов линейный поиск в худшем случае (когда искомого элемента нет в массиве) обработает все 1024 элемента, но бинарным поиском достаточно обработать log2(1024) = 10 элементов. Такой результат достигается за счет того, что после первого шага цикла область поиска сужается до 512 элементов, после второго – до 256 и т.д.

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

Посмотрите также, как реализуется алгоритм двоичного поиска на Си.

8 thoughts on “Двоичный (бинарный) поиск С++

  1. В примере кода ошибка, если ввести, например, число 13, то последняя итерация будет уже за границей массива(midd = 12). Программа не падает и даёт верный результат, потому что за границей массива есть память доступная процессу.

    1. int midd = 0;
      while (1)
      {
      if(midd <=n)
      {
      midd = (left + right) / 2;
      if (key arr[midd]) // если искомое больше значения в ячейке
      {
      left = midd + 1; // смещаем левую границу поиска
      }else // иначе (значения равны)
      {
      cout<<"key[ "<<midd<<" ] = "<<key<<endl;
      return midd; // функция возвращает индекс ячейки
      }
      }
      } return -1;
      }

      Исправил, вроде, если не трудно проверь

      1. n — это что? это ваше значение которое вы ищите в массиве

  2. Например масив из 20 чисел
    Почему я ввожу в поиске n-ное число
    Мне показывает индекс до него?

    1. Потому что в c++ индексация нулевая (то есть первый элемент для человека – это нулевой элемент для языка, второй элемент для человека – это первый элемент для языка и т.д.)

  3. Всё норм, только я бы прибавил к индексу единицу, чтобы пользователю выводилось “Указанное число находится в ячейке с индексом: …” и если число в массиве находится под индексом 2, для человека это будет индекс 3, так как массив считается с нуля, а не с единицы

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *