|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : zugr 2:5020/400 26 Mar 2002 16:10:37
To : All
Subject : Re: Binary search with duplicate values
--------------------------------------------------------------------------------
Andrew Doroshev писал:
> ...
> Example, please. Я вполне серьёзно. Я не знаю примеров более быстрого поиска,
> чем деление пополам.
> ...
Если данные в масиве характеризуются, плавностью возрастания(убывания) и
могут быть охарактеризованы каким либо числовым значением, то очень
может помочь интегральный поиск.
a - левый индекс
b - правый
f(a) - числовая величина характеризующая a-й элемент массива
f(b) - числовая величина характеризующая b-й элемент массива
F - величина индекс которой ищем
i - предполагаемое положение искомой величины в масиве
b-a
i=( --------- * F ) + a
f(b)-f(a)
соответственно либо найдём, либо ищем влево если f(i)>F, иначе ищем вправо.
Если массив будет не плавный, то на некоторых итерациях начнёт принимать
значения близкие или даже равный а или b, здесь можно рекомендовать
несколько выходов из ситуации.
1) Попеременно использовать бинарную и интегральную итерацию.
2) При впаданиии в подобный колапс вероятно искомое значение очень
близко, и перейти к линейному поиску (или поиску с шагом)
...
--- ifmail v.2.15dev5
* Origin: INN server ISP Unikon (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
