|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Protopopov Michael 2:5020/400 25 Jan 2002 16:04:24
To : Max Vlasov
Subject : Re: Бинарный поиск диапазона значений
--------------------------------------------------------------------------------
> Есть ли какие-нибудь мысли как можно эффективное реализовать бинарный
поиск
> в отсортированном массиве, но который возвращал бы не индекс элемента, а
> диапазон индексов элементов. То есть в массиве могут быть повторяющиеся
> элементы. Линейный поиск после успешного бинарного не подходит, потому что
> повторяющиеся элементы могут занимать половину объема данных и это
> становится неэффективным. Видимо это тоже должен быть бинарный поиск, но
> немного по другому критерию.
Писал я в свое время аналогичную вещь...
Общая идея такая.
Hадо преобразовать бинарный поиск, чтобы он искал первое(последнее)
вхождение эл-та.
Это делается так (для поиска первого вхождения):
При равенстве берешь найденный эл-т в качестве правой границы и продолжаешь
поиск до схождения к одному эл-ту.
Далее надо проверить его и следующий.
Для последнего вхождения аналогично.
Hадо также реализовать на основе бинарного поиска "Предварительный поиск".
Он должен остановиться в тот момент, когда следующая проба дает равенство и
вернуть найденный интервал (не следующий).
Далее собираем все вместе.
1. Осуществляем предварительный поиск. Пусть найденный интервал будет (a1,
a2).
2. Hаходим первое вхождение, но уже по интервалу (a1, a1+(a2-a1)/2), а не
по всему массиву.
3. Hаходим последнее вхождение, по интервалу (a1+(a2-a1)/2, a2)
Hасколько я помню, в этих алгоритмах надо внимательно следить за "краевыми"
эффектами, т.е когда поиск сходится к краям массива.
Михаил Протопопов.
--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.Mail.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Бинарный поиск диапазона значений 