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


Задача

6/7

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

Теория Нажмите, чтобы прочитать/скрыть

Двоичный поиск
Двоичный (или бинарный) поиск является эффективным алгоритмом поиска, выполняется он быстрее чем линейный поиск. Например, для массива из 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.