Модуль: C++. Линейный и двоичный поиск элементов в массиве


6. Двоичный поиск

☰ Теория

Двоичный поиск
Двоичный (или бинарный) поиск является эффективным алгоритмом поиска, выполняется он быстрее чем линейный поиск. Например, для массива из 1024 элементов линейный поиск в худшем случае (когда искомого элемента нет в массиве) обработает все 1024 элемента, но бинарным поиском достаточно обработать 10 элементов. Такой результат достигается за счет того, что после первого шага цикла область поиска сужается до 512 элементов, после второго – до 256 и т.д.
 
Недостатками такого алгоритма является требование упорядоченности данных, а также возможности доступа к любому элементу данных за постоянное (не зависящее от количества данных) время. Таким образом алгоритм не может работать на неупорядоченных массивах.
 
Алгоритм
  1. Выбрать средний элемент A[c] и сравнить с X.
  2. Если X = A[c], то нашли (стоп).
  3. Если X < A[c], искать дальше в первой половине.
  4. Если X > A[c], искать дальше во второй половине.
     
Реализация
L = 0; R = N; // начальный отрезок
while ( L < R - 1)
{
	c = (L + R) / 2; // нашли середину
	if ( X < A[c] )  // сжатие отрезка
	    R = c;
	else 
	    L = c;
}
if ( A[L] == X)
    cout << "A[" << L << "]=" << X;
else
    cout << "Not found";


где:
А - исходный массив,
N - размер массива,
X - искомое число,

Возможны и другие реализации.
Например, с использованием досрочного выхода из цикла 
L = 0; R = N - 1; 
while ( R >= L)
{
	c = (L + R) / 2; 
	if ( X == A[c] )
	{  
	    nX = c;
	    break;
	}
	if (X < A[c]) R = mid - 1;
	if (X > A[c]) L = mid + 1;
}
if ( nX < 0)
    cout << "Not found";
else
    cout << "A[" << nX << "]=" << X;

В заданном массиве, отсортированном по возрастанию необходимо найти значение элемента равного значению Х, используя двоичный поиск. X вводится с клавиатуры. Доработайте программу, чтобы она решала задачу Нумерация элементов начинается с нуля. В случае если такого элемента нет, программа должна выводить Not found.
Вставьте недостающие фрагменты кода
C++ 
#include<iostream> 
using namespace std; 
main() 
{	
  const int Nmax=1000; 	
  int A[Nmax], i, L, R, X, N, c;	 
  cin >> N; 
  for (i=0; i<N; i++) 
    cin >> A[i]; 
  cin >> X; 
  L = 0; R = N;       
  while ( L < R-1 )     
       cout << "A["<< L << "]=" << X; 
  else cout << "Not found"; 
}
     

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Комментарий учителя

Результат проверки программы 
Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!