Delphi World - Бинарный поиск с определением ближайших узлов
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Бинарный поиск с определением ближайших узлов

В ряде случаев (в частности, в задачах интерполяции) приходится выяснять, где по отношению к заданному упорядоченному массиву действительных чисел располагается заданное действительное число. В отличие от поиска в массиве целых чисел, заданное число в этом случае чаще всего не совпадает ни с одним из чисел массива, и требуется найти номера элементов, между которыми это число заключено.

Один из наиболее быстрых способов этого является бинарный поиск, характерное число операций которого имеет порядок 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) {right=n-1;break;}
        if(array[right] > value) break;
        left=right; inc<<=1;
      }
    }
  }
  /* начальное приближение плохое - 
  за область поиска принимается весь массив */
  else {left=0;right=n-1;}
  /* ниже алгоритм бинарного поиска требуемого интервала */
  while(left>1;
    if(value>=array[node]) left=node;
    else right=node;
  }
  /* возвращаем найденную левую границу, 
  обновив старое значение результата */
  return(*old=left);
}

Замечание: для успешной работы алгоритма целесообразно при первичном запуске положить *old=-1 или другое число, гарантирующее бинарный поиск на первом проходе.

Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования