Двоичный поиск.
В прошлом уроке мы рассмотрели алгоритм линейного поиска, однако это не
единственная возможность организовать поиск в массиве. Если у нас есть массив,
содержащий упорядоченную последовательность данных, то, в данном случае, очень
эффективен двоичный поиск.
Теория двоичного поиска.
Предположим, что переменные Lb и Ub содержат, соответственно, левую и правую
границы отрезка массива, где находится нужный нам элемент. Поиск мы всегда будем
начинать с анализа среднего элемента отрезка массива. Если искомое значение
меньше среднего элемента, мы переходим к поиску в верхней половине отрезка, где
все элементы меньше только что проверенного. Другими словами, значением Ub
становится (M (средний элемент) – 1) и на следующей итерации мы работаем с
половиной массива. Таким образом, в результате каждой проверки мы вдвое сужаем
область поиска. Так, в нашем примере, после первой итерации область поиска –
всего лишь три элемента, после второй остается всего лишь один элемент. Таким
образом, если длина массива равна 6, нам достаточно трех итераций, чтобы найти
нужное число.
Пример реализации.
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
int BinarySearch (int A[], int Lb, int Ub, int Key)
{
int M;
while(1){
M = (Lb + Ub)/2;
if (Key < A[M])
Ub = M - 1;
else if (Key > A[M])
Lb = M + 1;
else
return M;
if (Lb > Ub)
return -1;
}
}
void main(){
srand(time(NULL));
const long SIZE=10;
int ar[SIZE];
int key,ind;
// до сортировки
for(int i=0;i<SIZE;i++){
ar[i]=rand()%100;
cout<<ar[i]<<"\t";
}
cout<<"\n\n";
cout<<"Enter any digit:";
cin>>key;
ind=BinarySearch(ar,0,SIZE,key);
cout<<"Index - "<<ind<<"\t";
cout<<"\n\n";
}
|
Двоичный поиск - очень мощный метод. Посудите сами: например, длина массива
равна 1023, после первого сравнения область сужается до 11 элементов, а после
второй - до 255. Легко посчитать, что для поиска в массиве из 1023 элементов
достаточно 10 сравнений.
