# Questions tagged [search-algorithms]

Algorithms for finding an element in some specified data-structure (most commonly, in a tree).

45 questions
Filter by
Sorted by
Tagged with
47k views

### Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u ...
700 views

### An online algorithm to find the Pareto frontier elements

I'm looking for an online algorithm that takes a stream of elements and preserves the elements that are on the Pareto frontier (e.g. all non-dominated elements). For instance. Given the following ...
2k views

### Finding k'th smallest element from a given sequence only with O(k) memory O(n) time

Suppose that we read a sequence of $n$ numbers, one by one. How to find $k$'th smallest element just with using $O(k)$ cell memory and in linear time ($O(n)$). I think we should save first $k$ terms ...
24k views

### Why is the A* search heuristic optimal even if it underestimates costs?

A* search finds optimal solution to problems as long as the heuristic is admissible which means it never overestimates the cost of the path to the from any given node (and consistent but let us focus ...
6k views

### Greedy and backtracking solutions to an arrangement problem with constraints

I'm revising for my finals. I have found a pattern in past papers in terms of a recurring question, reworded coming up every year. But I've no idea what the marker actually wants... I've asked class ...
4k views

### Optimal algorithm to traverse all paths in the order of shortest path

I have to generate all possible paths in a directed, acyclic weighted graph with edge costs. I also have to sort them in order of shortest path. The simplest way that comes to mind is to do a depth-...
7k views

### How do I find the max and min value of an array in 3n/2−2 comparisons?

So I'm using this method to find the min and max value of an array simultaneously where I split the array into n/2 and n/2 parts. I then keep splitting each part until I have either a pair of numbers ...
3k views

### What's the fastest way to find the Kth smallest value in an unsorted list without sorting?

My initial algorithm: Compare element 0 with every other element, keeping track of how many elements are less than it. Repeat for each element until an element that is greater than exactly (k-1) ...
3k views

### What are the conditions that make the A* algorithm optimal over the other unidirectional search algorithms

I was wondering as what are the specific conditions which make the A* algorithm - optimal in terms of the node expansion over the other Unidirectional algorithms: When the same heuristic ...
2k views

### Data Structure For Closest Pair Problem

Suppose I have a list of distinct integers. I'm looking for a data structure that will support the operations search, insert, <...
173 views

### How to get the quick answer to the “Is there AT LEAST ONE subset that contains all given elements?” question if the set of subsets is very large?

I have a very large amount of objects that look like this: ...
567 views

### Algorithm to detect if word belongs to pushdown automaton

I am creating a simple program to detect if the given pushdown automaton accepts the given word, and I have a problem in finding an algorithm that does that. My thought at first would be to go ...
477 views

### Dijkstra’s versus Lowest-cost-first (best first), resolving some contradictions regarding complexity analysis

Our professor took three statements from various textbooks that seem to be a little contradictory regarding the complexity analysis of Dijkstra’s algorithm as well as the lowest-cost-first or best ...
1k views

### Problem with Cormen's treatment of the Rabin-Karp algorithm

I am reading chapter 32 - String Matching from the book "Introduction to Algorithms" 3rd edition Cormen et al. The Rabin-Karp Algorithm is not clear to me despite heaving read it several times. ...
47 views

### Finding the point with minimum x-ordinate, lying between two y-ordinates

Given a set of points $P=p_1,p_2,..p_n$ in $R^2$ in where $p_i=(x_i,y_i)$,finding the point with smallest x-ordinate having y-ordinates between $y_1$ and $y_2$, where $y_1$ and $y_2$ are given as ...
56k views

### Graph searching: Breadth-first vs. depth-first

When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)). Now, are ...
25k views

### Why is binary search faster than ternary search?

Searching an array of $N$ elements using binary search takes, in the worst case $\log_2 N$ iterations because, at each step we trim half of our search space. If, instead, we used 'ternary search', we'...
19k views

### Shortest Path on an Undirected Graph?

So I thought this (though somewhat basic) question belonged here: Say I have a graph of size 100 nodes arrayed in a 10x10 pattern (think chessboard). The graph is undirected, and unweighted. Moving ...
32k views

### How does an admissible heuristic ensure an optimal solution?

When using A* (or any other best path finding algorithm), we say that the heuristic used should be admissible, that is, it should never overestimate the actual solution path's length (or moves). How ...
8k views

### One element that differs in two arrays. How to find it efficiently?

I am preparing for a coding interview and I can't really figure out the most efficient way to solve this problem. Let's say we have two arrays consisting of numbers that are unsorted. Array 2 ...
1k views

### What is a lay explanation for universal search?

I am reading a book on a computer science topic but lack some of the prerequisite background. Normally when I run into terms I don't understand I simply look them up, but for Universal Search I simply ...
4k views

### Directed union-find

Consider a directed graph $G$ on which one can dynamically add edges and make some specific queries. Example: disjoint-set forest Consider the following set of queries: ...
1k views

### Finding a pair of non-overlapping bit vectors

I give you a list of $n$ bitvectors of width $k$. Your goal is to return two bitvectors from the list that have no 1s in common, or else to report that no such pair exists. For example, if I give you ...
793 views

### Why say that breadth-first search runs in time $O(|V|+|E|)$?

It's often stated (e.g., in Wikipedia) that the running time of breadth-first search (BFS) on a graph $G=(V,E)$ is $O(|V|+|E|)$. However, any connected graph has $|V|\leq |E|+1$ and, even in a non-...
4k views

### Minimum number of tree cuts so that each pair of trees alternates between strictly decreasing and strictly increasing

A gardener consider aesthetically appealing gardens in which the tops of sequential physical trees (eg palm trees) are always sequentially going up and down, that is: ...
12k views

### An efficient algorithm to find a shortest cycle including a specific vertex

We wish to find shortest cycle (if any cycle exists) that includes a special vertex $v$. We know if we run DFS on an undirected graph, back edges show us that there exists at least one cycle. This ...
3k views

### Can this algorithm still be considered a Binary Search algorithm?

While doing the second code kata (which asks you to implement a binary search algorithm five times, each time with a different method), I've come up with a slightly different solution which works as ...
11k views

### Find all intervals that overlap with a given interval

Note: I moved this question from stackoverflow.com I have an algorithmic problem where I would like to see if it can be solved in better than $O(n)$: I have given a table $T$ of $n$ elements where ...
668 views

### Is there any study or theory behind combining binary search and interpolation search?

I just read Can this algorithm still be considered a Binary Search algorithm? and recalled that a few years back I wrote an indexer/search for log files to find log entries in large plain text files ...
4k views

### All paths of less than a given length in a directed graph between couple of nodes

Counting all possible paths, or all possible paths with a given length, between a couple of nodes in a directed or undirected graph is a classical problem. Attention should be given to what all means, ...
1k views

### Is there any strategy to brute force search?

I don't know how to state it elegantly, but basically, I want to implement a brute force search algorithm, but there are many different ways that I could enumerate through the search space. This ...
4k views

### Is there a data structure for efficiently searching a string that contains a given substring?

This question arose from a practical problem: given a set of texts, find one, which contains a given string (not word). Let $S$ be a set of $n$ strings, and $l$ the length of the longest string in $S$...
2k views

### Does the A* algorithm visit every node?

I have been taught that the A* algorithm visits every node on the graph, like Dijkstra's does, prioritising nodes with the smallest cost. However, visualisations of the algorithm, such as this one, ...
420 views

### Searching a sorted array to find the $k$ closest values to a target value $T$

Let $A$ be a sorted array of $N$ values. I am interested in finding the index $j$ such that the elements $A_j, A_{j + 1}, ..., A_{j + k - 1}$ have the $k$ closest values to the given target value $T$. ...
44 views

### Maximal Elements in a Lower Set

I have a collection of objects, and a feasibility property for sets of objects which is slow to compute. If a set is feasible then so is any subset. For example, it could be whether the set of things ...
1k views

### Is there a more efficient algorithm than backtracking/dynamic programming?

Consider the following game: One day a castle is attacked at sunrise (by surprise) by n soldiers. Each soldier carries a canon and a rifle. The castle has strength s. On the first day each ...
3k views

### How is the oracle function for Grover's Search algorithm obtained?

I've been using the IBM quantum experience to learn about and simulate Grover's algorithm. When they create the algorithm, they use a different set of gates depending on which oracle function $f(x)$ ...
680 views

### Given a set of string patterns, find which ones match a particular string

I have an array of known patterns with optional wildcards. For example this array that has 5 patterns: ab*e hkl abcd* ab sdfs?f now I need to find the elements within the array that match an ...
215 views

### Find all neighbors at a certain distance, in 3 dimensions

I have two algorithms which I would like to implement: First, given a (very long) list $\{\mathbf{r}_{i}\}_{i=1}^{n}\subset \mathbb{R}^{3}$, a point $p \in \mathbb{R}^{3}$, and a distance $d>0$, ...
959 views

### String matching for wildcard-based records

Let's say that we have a string "1.2.3" and want to find a match for it in the following records: 1.2.9 1.4.5 1.*.3 For each ...
136 views

### Searching for multiple partial phrases so that one original phrase can not match multiple search phrases

Given a predefined set of phrases, I'd like to perform a search based on user's query. For example, consider the following set of phrases: ...
30 views

### What solution to apply for finding the optimal parameters?

For a study, I have a system (black-box) that requires an input in the form of an array with 4 values (input_array) and depending on their values it produces an ...
2k views

### What data structure would help find nearby coordinates quickly?

I need to write a program that does the following: Take an input list of objects whose properties include latitude and longitude to, say, 5 decimal places Store them in a data structure once Provide ...
Egg drop. Suppose that you have an $n$-story building (with floors 1 through $n$) and plenty of eggs. An egg breaks if it is dropped from floor $T$ or higher, and does not break otherwise. Your goal ...