Tag Archives: binary

Binary search over floating point representations

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

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

Counting inversions via rank queries

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

Sum of heights in a binary tree

Executive summary: every year when teaching data structures I always forget how to analyze the cost of building a binary heap, which amounts to summing the heights of all the nodes in a full binary tree. So I’m writing down … Continue reading

Posted in math, teaching | Tagged , , , , , , , | 2 Comments