 |
|
Поиск в строках, массивах, последовательностях.
Бинарный поиск в упорядоченном действительном массиве с определением ближайших узлов.
© Валерий Ф. Никитин
В ряде случаев (в частности, в задачах интерполяции) приходится выяснять, где по отношению к заданному упорядоченному массиву действительных чисел располагается заданное действительное число. В отличие от поиска в массиве целых чисел, заданное число в этом случае чаще всего не совпадает ни с одним из чисел массива, и требуется найти номера элементов, между которыми это число заключено.
Один из наиболее быстрых способов этого является бинарный поиск, характерное число операций которого имеет порядок log2(n), где n -- число элементов массива. При многочисленных обращениях к этой процедуре число операций будет равно m log2(n) (m -- число обращений). Ускорения этой процедуры можно добиться за счет сохранения предыдущего результата операции и попыток поиска при новом обращении в ближайших узлах массива с дальнейшим расширением области поиска в случае неуспеха.
При этом в наихудших случаях число операций будет больше (примерно в 2 раза) по сравнению с бинарным поиском, но обычно при m значительно большим, чем log2(n) удается довести порядок числа операций до m, то есть сделать его почти независимым от размера массива.
Важным примером применения подобного алгоритма является картирование области: по заданному массиву RGB-палитры, соответствующему 'уровням' карты, раскрасить эту область, определив цвет каждого пиксела. Значение, соответствующее пикселу, считается заданным (найденным каким-либо внешним по отношению к программе раскрашивания способом); по нему определяется, между какими уровнями карты оно находится, а по этим номерам определяется его цвет, получаемый из палитры.
Число уровней при этом может быть достаточно большим, изменение же уровня между соседними пикселами -- чаще всего слабым. В этом случае ускорение, порождаемое алгоритмом по сравнению со стандартным бинарным поиском, является весьма существенным.
Задача ставится так. Дан упорядоченный массив действительных чисел array размерности n, проверяемое значение value и начальное приближение узла old. Требуется найти номер узла res массива array, такой, что array[res]<=value<array[res+1]
Алгоритм работает следующим образом.
1. Определяется, лежит ли проверяемое value за пределами массива array. В случае value<array[0] возвращается -1, в случае value>array[n-1] возвращается n-1.
2. Иначе проверяется: если значение old лежит за пределами индексов массива (т.е. old<0 или old>=n, то переходим к обычному бинарному поиску, установив левую границу left=0, правую right=n-1.
3. Иначе переходим к выяснению границ поиска. Устанавливается left=right=old, inc=1 -- инкремент поиска.
4. Проверяется неравенство value>=array[old]. При его выполнении переходим к следующему пункту (5), иначе к пункту (7).
5. Правая граница поиска отводится дальше: right=right+inc. Если right>=n-1, то устанавливается right=n-1 и переходим к бинарному поиску.
6. Проверяется value>=array[right]. Если это неравенство выполняется, то левая граница перемещается на место правой: left=right, inc умножается на 2, и переходим назад на (5). Иначе переходим к бинарному поиску.
7. Левая граница отводится: left=left-inc. Если left<=0, то устанавливаем left=0 и переходим к бинарному поиску.
8. Проверяется value<array[left]. При выполнении правая граница перемещается на место левой: right=left, inc умножается на 2, переходим к пункту (7). Иначе к бинарному поиску.
9. Проводится бинарный поиск в массиве с ограничением индексов left и right. При этом каждый раз интервал сокращается примерно в 2 раза (в зачисимости от четности разности), пока разность между left и right не достигнет 1. После этого возвращаем left как результат, одновременно присваивая old=left.
Ниже приведена программа на C, реализующая алгоритм поиска в упорядоченном массиве действительных чисел.
/* Search within a real ordered array.
Parameters:
value -- the sample,
old -- previous result,
array,n -- the array and its dimension.
Returns: Left node of the array segment matching the sample.
In case the sample is out of the array, returns -1 (less than
left boundary) or (n-1) (more than the right boundary).
*/
int fbin_search(float value,int *old,float *array,int n) {
register int left,right;
/* проверка позиции за пределами массива */
if(value < array[0]) return(-1);
if(value >= array[n-1]) return(n-1);
/* процесс расширения области поиска. Вначале проверяется валидность
начального приближения */
if(*old>=0 && *old<n-1) {
register int inc=1;
left = right = *old;
if(value < array[*old]) {
/* область расширять влево */
while(1) {
left -= inc;
if(left <= 0) {left=0;break;}
if(array[left] <= value) break;
right=left; inc<<=1;
}
}
else {
/* область расширять вправо */
while(1) {
right += inc;
if(right >= n-1) {right=n-1;break;}
if(array[right] > value) break;
left=right; inc<<=1;
}
}
}
/* начальное приближение плохое -
за область поиска принимается весь массив */
else {left=0;right=n-1;}
/* ниже алгоритм бинарного поиска требуемого интервала */
while(left<right-1) {
register int node=(left+right)>>1;
if(value>=array[node]) left=node;
else right=node;
}
/* возвращаем найденную левую границу,
обновив старое значение результата */
return(*old=left);
}
Замечание: для успешной работы алгоритма целесообразно при первичном запуске положить *old=-1 или другое число, гарантирующее бинарный поиск на первом проходе.
Вверх по странице, к оглавлению и навигации.