Двоичный поиск
Двоичный (или бинарный) поиск является эффективным алгоритмом поиска, выполняется он быстрее чем линейный поиск. Например, для массива из 1024 элементов линейный поиск в худшем случае (когда искомого элемента нет в массиве) обработает все 1024 элемента, но бинарным поиском достаточно обработать 10 элементов. Такой результат достигается за счет того, что после первого шага цикла область поиска сужается до 512 элементов, после второго – до 256 и т.д.
Недостатками такого алгоритма является требование упорядоченности данных, а также возможности доступа к любому элементу данных за постоянное (не зависящее от количества данных) время. Таким образом алгоритм не может работать на неупорядоченных массивах.
Алгоритм
- Выбрать средний элемент
A[c] и сравнить с X.
- Если
X = A[c], то нашли (стоп).
- Если
X < A[c], искать дальше в первой половине.
- Если
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;