Tag Archives: search

Binary search over floating point representations

Posted on January 2, 2023 by Brent

I got some good feedback on my last post about binary search, and thought it was worth a follow-up post. An important fix First things first: commenter Globules pointed out that doing (l+r) `div` 2 can overflow; my initial, glib … Continue reading →

Posted in haskell | Tagged , , , | Leave a comment

Competitive programming in Haskell: better binary search

Posted on January 1, 2023 by Brent

Binary search is a workhorse of competitive programming. There are occasional easy problems where binary search is the solution in and of itself; more often, it’s used as a primitive building block of more complex algorithms. It is often presented … Continue reading →

Posted in competitive programming, haskell | Tagged , , | 23 Comments

Competitive programming in Haskell: BFS, part 4 (implementation via STUArray)

Posted on November 17, 2021 by Brent

In a previous post, we saw one way to implement our BFS API, but I claimed that it is not fast enough to solve Modulo Solitaire. Today, I want to demonstrate a faster implementation. (It’s almost certainly possible to make … Continue reading →

Posted in competitive programming, haskell | Tagged , , , , , , | 3 Comments

Competitive programming in Haskell: BFS, part 3 (implementation via HashMap)

Posted on October 29, 2021 by Brent

In a previous post, I showed how we can solve Modulo Solitaire (and hopefully other BFS problems as well) using a certain API for BFS, and we also explored some alternatives. I had a very interesting discussion with Andrey Mokhov … Continue reading →

Posted in competitive programming, haskell | Tagged , , , , , | 6 Comments

Competitive programming in Haskell: BFS, part 2 (alternative APIs)

Posted on October 18, 2021 by Brent

In my last post, I showed how we can solve Modulo Solitaire (and hopefully other BFS problems as well) using a certain API for BFS, which returns two functions: one, level :: v -> Maybe Int, gives the level (i.e. … Continue reading →

Posted in competitive programming, haskell | Tagged , , , , | 6 Comments

Competitive programming in Haskell: BFS, part 1

Posted on October 14, 2021 by Brent

In a previous post, I challenged you to solve Modulo Solitaire. In this problem, we are given a starting number and are trying to reach in as few moves as possible. At each move, we may pick one of up … Continue reading →

Posted in competitive programming, haskell | Tagged , , , , | 5 Comments

Counting inversions via rank queries

Posted on December 18, 2019 by Brent

In a post from about a year ago, I explained an algorithm for counting the number of inversions of a sequence in time. As a reminder, given a sequence , an inversion is a pair of positions such that and … Continue reading →

Posted in haskell | Tagged , , , , , , , , , | 4 Comments