# Questions tagged [searching]

For questions about various search algorithms.

7 questions
Filter by
Sorted by
Tagged with
6k views

### 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 ...
18k views

### 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 ...
7k views

### Median of medians algorithm

I am referring to the algorithm presented here used to find a good pivot: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm My ...
122 views

### Searching for a point on the real line

A pin is dropped at a random point $p$ on the real line, with $p$ determined from a normal distribution with mean $0$ and standard deviation $\sigma$. You are dropped on the real line at $x=0$ and ...
2k views

### 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. ...
Suppose i have a graph $G$ of $n$ nodes. For each node someone has given us a recipe $R$ how to replace the node with a graph. So for node $i$, i have $m_i$ choices of graphs to replace it with. Thus, ...