# Questions tagged [searching]

For questions about various search algorithms.

116 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 ...
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. ...
301 views

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

599 views

### Prove that a connected undirected graph G is bipartite if and only if there are no edges between nodes at the same level in any BFS tree for G

My question is in the title but to restate: Prove that a connected undirected graph $G$ is bipartite if and only if there are no edges between nodes at the same level in any BFS tree for $G$. (BFS ...
750 views

### Weakly unimodal function using Golden Section Search

I was going through the Golden Section Search https://en.wikipedia.org/wiki/Golden_section_search and as I understand it should work for every unimodal function. Here, the definition of unimodal ...
161 views

### How to search between $n$ candidates from unknown position?

It might be involved more with search algorithm but I cannot think of any of them. Here is the problem: You are in a corridor that stretches infinitely in both directions. Your room is somewhere ...
2k views

### How to apply DFS on a disconnected graph.

I was wondering how to go about solving a problem with disconnected graphs and depth-first search. Here is an example of a disconnected graph. How would I go through it in DFS? My current ...
71 views

### Smart enumeration of a subset of graphs obtained from a parent graph

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, ...
521 views

### Algorithm to find difference between two array members

I have a question concerning algorithms and time complexity(analysis).So I have a field A,which is sorted and has natural numbers where n is >=2(ascending order).How would you write an algorithm which ...
36 views

### How to implement an algorithm for specific kinds of search in a graph

Imagine i have a graph called G. G has some parts. In one part, every node describes a person. I have another part in G which contains interests as nodes. ( Imagine that person A likes music. So, ...
39 views

### Does this search method exist and what is it called?

I would like to search some function $f(x)$ "greedily" for a certain condition. Assume the condition $c = f(x_1)$ returned by this function is currently false and I can increase the input $x$ to the ...
60 views

### Exploiting geometric invariants via group theory

Let $T$ be the set of all plane triangles. The problem is to find $t \in T$ s.t.h. a predicate $P(t)$ holds. At present, I'm doing this by a form of randomized search procedure (effectively via a ...
36 views

### Need help understanding a simplification in a simultaneous search model.

The problem I am trying to solve is $\max_{k \in \mathbb{N}} \int_0^1 u d F(u)^k - ck$, where the associated utility is an iid random variable U following $F(\cdot)$ on [0,1]. $c > 0$ is the ...
724 views

### Searching Algorithm

A company database has 10,000 customers sorted by last name, 20% of whom are known to be good customers. When looking up a customer’s record in the database, the good customers account for 60%. Two ...
755 views

### How to use binary search to find a function

I am reading somewhere that $$(\phi'(y))^{-1}=y^{-c_1}+y^{-c_2},$$ $c_1,c_2$ are some numbers, can be solved for $\phi$ using binary search. I am surprised because binary search binary search is used ...
31 views

### Binary search in merged arrays.

Given two arrays, sorted by ascending. Result array is first array and second at the end of first. Example: [1, 4, 7, 11] and [2, 3, 5]. Result array is [1, 4, 7, 11, 2, 3, 5]. How to find element ...
228 views

### Searching for random items in a set of lists

This is a programming question, but I'm interested in the math behind it so I think it's better asked here. Say I have a list of items and I'm looking for one item in the list that satisfies a ...
39 views

### Having objects trajctories and directions how to find where objects traverse same path?

I have N objects that travel on some trajectories (unique for each object). At each agent curve point we can get object speed (direction). Having some distance ...