ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Oleg I. Khovayko                     2:5020/400     23 Feb 2002  00:48:32
 To : Andrew Doroshev
 Subject : Re: Поиск диапазона в массиве
 -------------------------------------------------------------------------------- 
 

 
 > индекс. Естественно, первое, что приходит в голову - деление пополам,
 > О(log n), однако для двух границ получим удвоение времени поиска, что не
 > есть хорошо.
 
 делать надобно тремя половинными делениями:
 
 1. Сначала половинным делением ищешь интервал, содержащий твое число,
 то есть m[lo] < X < m[hi].
 Как только апробация по адресу m[(hi+lo)/2] сработала: X == m[(hi+lo)/2], 
 то отсюда уже делаешь два независимых половинных деления, 
 ища границы области...
 -- 
 #include <best/regards.hpp>
 Oleg I. KHOVAYKO  
 (301)435-5885 || WEB: http://olegh.spedia.net
 --- ifmail v.2.15dev5
  * Origin: National Center for Biotechnology Information (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Поиск диапазона в массиве   Andrew Doroshev   22 Feb 2002 07:00:22   Re: Поиск диапазона в массиве   Oleg I. Khovayko   23 Feb 2002 00:48:32   Поиск диапазона в массиве   Dmitry Koren   27 Feb 2002 20:02:42   Re: Binary search with duplicate values   Andrew Doroshev   28 Feb 2002 20:28:03   Binary search with duplicate values   Sashka Yackubtchick   03 Mar 2002 06:23:50   Re: Binary search with duplicate values   Andrew Doroshev   07 Mar 2002 13:52:08   Re: Binary search with duplicate values   zugr   26 Mar 2002 16:10:37