Ищет общую функцию `bisect`

Question

Я ищу работу bisect в Haskell, как у bisect_left() Python и друзей. Ввод будет нижней границей, верхней границей, неубывающей функцией (Ord a) => (Int-> a), которая должна быть определена для всех целых чисел между нижней и верхней границей и значением поиска. Возвращаемое значение является наивысшим целым числом i, где lower <= i <= upper и f(i) < search_term. Производительность должна быть O (log (n)).

Hoogling для этого:

(Ord a)=>(Int->a)->Int->Int->a->Int 

не дает никаких результатов.

Существует ли стандартный библиотечный оператор поиска в библиотеке где-нибудь?

Answer 1

Пакет Ross Paterson's binary-search пакета Hackage делает то, что вы ищете. В частности, см searchFromTo, который имеет тип подпись

searchFromTo :: Integral a => (a -> Bool) -> a -> a -> Maybe a 

Как Тихон указывает, [a] в Haskell является связанный список, а не массив. Поскольку связанные списки поддерживают только последовательный доступ, невозможно получить логарифмический поиск по времени в структуре данных [a]. Вместо этого вы должны использовать подлинную структуру данных массива - см. Библиотеку vector для предпочтительной реализации массивов.

Dan Doel написал семейство бинарных функций поиска для изменяемых векторов в векторном пакете: см Data.Vector.Algorithms.Search в его vector-algorithms библиотеке. В отличие от библиотеки Росса Патерсона, которая предоставляет чистый API, API в Data.Vector.Algorithms.Search является монадическим (то есть он должен быть запущен в монаде ST или монаде IO).

Answer 2

Функция, подобная bisect_left (при условии, что я правильно прочитал ее документацию), действительно не существует для списков.

Это имеет смысл - поскольку у вас нет произвольного доступа в O (1) в списках (помните, что списки Haskell - это связанные списки, а Python использует нечто большее, как вектор), вы не могли бы получить двоичный поиск O (logn).

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

Вкратце - бинарный поиск не имеет смысла на списков. Если вы много работаете, вам, вероятно, нужна другая структура данных. В частности, посмотрите на Data.Set, который использует внутренние двоичные деревья.

Answer 3

binary_search :: Ord a, Integral b => (b -> a) -> b -> b -> a -> b 
binary_search f low hi a = go low hi 
    where 
     go low hi | low + 1 == hi = low 
     go low hi = go low' hi' 
      where 
       mid = (low + hi) `div` 2 
       (low',hi') = if f mid < a then (mid,hi) else (low, mid) 

(Это может иметь погрешность не совсем по одному.)