Основи програмування на С ++ для початківців

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

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

Предположим, что массив из 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 думки про "Двоичный (бинарный) поиск С

  1. У прикладі коду помилка, якщо ввести, например, число 13, то остання ітерація буде вже за кордоном масиву(midd = 12). Програма не падає і дає вірний результат, тому що за кордоном масиву є пам'ять доступна процесу.

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

      виправив, начебто, якщо не важко перевір

      1. n - це що? це ваше значення яке ви шукайте в масиві

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

    1. Тому що в c ++ індексація нульова (тобто перший елемент для людини – це нульовий елемент для мови, другий елемент для людини – це перший елемент для мови і т.д.)

  3. Все норм, Все норм, Все норм “Указанное число находится в ячейке с индексом: …” Все норм 2, Все норм 3, Все норм, а не з одиниці

залишити коментар

Ваша електронна адреса не буде опублікований. Обов'язкові поля позначені * *