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

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

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

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

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

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

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

Пример:

#include <iostream>
using namespace std;

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

		if (left > right)          // если границы сомкнулись 
			return -1;
	}
}

int main()
{
	setlocale (LC_ALL, "rus");
	
	const int SIZE = 12;
	int array[SIZE] = {};
	int key = 0;
	int index = 0; // индекс ячейки с искомым значением

	for (int i = 0; i < SIZE; i++) // заполняем и показываем массив
	{
		array[i] = i + 1;
		cout << array[i] << " | ";
	}
	
	cout << "\n\nВведите любое число: ";
	cin >> key;
	
	index = Search_Binary (array, 0, SIZE, key);

	if (index >= 0) 
		cout << "Указанное число находится в ячейке с индексом: " << index << "\n\n";
	else
		cout << "В массиве нет такого числа!\n\n";
		
	return 0;
}

#include <iostream>

using namespace std;

// функция с алгоритмом двоичного поиска

int Search_Binary (int arr[], int left, int right, int key)

{

int midd = 0;

while (1)

{

midd = (left + right) / 2;

if (key < arr[midd]) // если искомое меньше значения в ячейке

right = midd - 1; // смещаем правую границу поиска

else if (key > arr[midd]) // если искомое больше значения в ячейке

left = midd + 1; // смещаем левую границу поиска

else // иначе (значения равны)

return midd; // функция возвращает индекс ячейки

if (left > right) // если границы сомкнулись

return -1;

}

int main()

{

setlocale (LC_ALL, "rus");

const int SIZE = 12;

int array[SIZE] = {};

int key = 0;

int index = 0; // индекс ячейки с искомым значением

for (int i = 0; i < SIZE; i++) // заполняем и показываем массив

{

array[i] = i + 1;

cout << array[i] << " | ";

}

cout << "\n\nВведите любое число: ";

cin >> key;

index = Search_Binary (array, 0, SIZE, key);

if (index >= 0)

cout << "Указанное число находится в ячейке с индексом: " << index << "\n\n";

else

cout << "В массиве нет такого числа!\n\n";

return 0;

}

Результат:

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

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

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

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

Анна:
15.11.2016 в 22:36
Спасибо. Очень подробно и понятно совсем начинающему….
Ответить
Виктор:
29.01.2017 в 09:54
В примере кода ошибка, если ввести, например, число 13, то последняя итерация будет уже за границей массива(midd = 12). Программа не падает и даёт верный результат, потому что за границей массива есть память доступная процессу.
Ответить
1. Никита:
  04.04.2017 в 13:55
  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. Ян:
    13.02.2019 в 23:22
    if(midd <=n)
    n — это что?
  2. k00priz:
    08.12.2019 в 09:25
    n — это что? это ваше значение которое вы ищите в массиве
Yura:
19.05.2019 в 12:01
Например масив из 20 чисел
Почему я ввожу в поиске n-ное число
Мне показывает индекс до него?
Ответить
1. Nikita:
  16.04.2021 в 18:51
  Потому что в c++ индексация нулевая (то есть первый элемент для человека – это нулевой элемент для языка, второй элемент для человека – это первый элемент для языка и т.д.)
  Ответить
Snale:
28.01.2022 в 01:28
Всё норм, только я бы прибавил к индексу единицу, чтобы пользователю выводилось “Указанное число находится в ячейке с индексом: …” и если число в массиве находится под индексом 2, для человека это будет индекс 3, так как массив считается с нуля, а не с единицы
Ответить