Articles of searching

Twenty questions against a liar

Here’s one that popped into my mind when I was thinking about binary search. I’m thinking of an integer between 1 and n. You have to guess my number. You win as soon as you guess the correct number. If your guess is not correct, I’ll give you a hint by saying “too high” or […]

The “find my car” problem: proper interpretation and solution?

This has been asked at least twice here, but both questions have accepted answers which are wrong. I don’t really know any good way to draw attention to the question besides asking again and being a bit more careful about not accepting incorrect or incomplete answers, so here goes. Say I am standing at the […]

Median of medians algorithm

I am referring to the algorithm presented here used to find a good pivot: My question is I don’t quite understand why the elements have to be divided specifically into groups of 5. Why not some other number?

Algorithm wanted: Enumerate all subsets of a set in order of increasing sums

I’m looking for an algorithm but I don’t quite know how to implement it. More importantly, I don’t know what to google for. Even worse, I’m not sure it can be done in polynomial time. Given a set of numbers (say, {1, 4, 5, 9}), I want to enumerate all subsets of this set (its […]

Lower bound for finding second largest element

In a recent discussion, I came across the idea of proving a lower bound for the number of comparisons required to find the largest element in an array. The bound is $n – 1$. This is so because the set of comparisons performed by every such algorithm looks like a tournament tree, which always has […]