|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Doroshev 2:5020/400 28 Feb 2002 20:28:03
To : Dmitry Koren
Subject : Re: Binary search with duplicate values
--------------------------------------------------------------------------------
Dear Dmitry Koren!!
> AD> Есть уже упорядоченный по возрастанию массив чисел, причём с
> AD> повторениями. Для заданного числа надо найти минимальный и
> AD> максимальный индекс. Естественно, первое, что приходит в голову -
> AD> деление пополам, О(log n), однако для двух границ получим удвоение
> AD> времени поиска, что не есть хорошо.
> Hе понимаю, в чём пpоблема. Имеется УПОРЯДОЧЕHHЫЙ массив чисел, напpимеp
> 1 5 7 8 8 8 9 12 13 17 17 ...
> Пpосто ищешь и сpавниваешь, занося в пеp-ые iMax и iMin соотв. индексы.
Суха теория, мой друг...
Последовательный поиск при 25*10Е6 элементах в массиве вещь небыстрая.
Это по техзданию, реально конечно меньше, при тестировании пока где то
до 10Е4.
А отладить двоичный поиск, если в массиве есть повторы, мне не удалось.
Пришлось вводить дополнительные проверки. В конце поиска, когда разница
"верхняя граница" - "нижняя граница" <= 1 ответ иногда на единицу
отличается от правильного.
Если делал что-то в роде
array={1 5 8 8 8}
b_search(-1)=0,0
b_search(0)=0,0
b_search(1)=0,1
b_search(2)=1,1
b_search(8)=2,5
b_search(9)=5,5
чем нибудь получше перебора - пиши
Andrew Doroshev
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
