Questions tagged [search-algorithms]

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

Filter by
Sorted by
Tagged with
86 votes
8 answers
59k 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 ...
malexmave's user avatar
  • 985
59 votes
3 answers
31k 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'...
The Mean Square's user avatar
42 votes
9 answers
63k 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 ...
curryage's user avatar
  • 531
32 votes
5 answers
4k views

Finding interesting anagrams

Say that $a_1a_2\ldots a_n$ and $b_1b_2\ldots b_n$ are two strings of the same length. An anagramming of two strings is a bijective mapping $p:[1\ldots n]\to[1\ldots n]$ such that $a_i = b_{p(i)}$ ...
Mark Dominus's user avatar
  • 1,537
27 votes
2 answers
2k views

How do I find my wife in a supermarket?

If two people are lost in a maze, is there an algorithm that they can both use to find each other without having previously agreed what algorithm they will be using? I think there are some ...
jl6's user avatar
  • 373
24 votes
5 answers
14k views

The purpose of grey node in graph depth-first search

In many implementations of depth-first search that I saw (for example: here), the code distinguish between a grey vertex (discovered, but not all of its neighbours was visited) and a black vertex (...
user6805's user avatar
  • 343
22 votes
7 answers
10k 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 ...
Konstantino Sparakis's user avatar
22 votes
3 answers
42k 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 ...
Ashwin's user avatar
  • 261
19 votes
2 answers
21k 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 ...
gfppaste's user avatar
  • 487
17 votes
4 answers
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 ...
Craig Gidney's user avatar
  • 5,852
16 votes
2 answers
7k views

How to implement AO* algorithm?

I have noticed that different data structures are used when we implement search algorithms. For example, we use queues to implement breadth first search, stacks to implement depth-first search and min-...
Zhang's user avatar
  • 161
15 votes
2 answers
5k views

Why is the base used to compute hashes in Rabin–Karp always primes?

The Rabin–Karp string matching algorithm requires a hash function which can be computed quickly. A common choice is $$ h(x_0\ldots x_n) = \sum_{i=0}^n b^i x_i, $$ where $b$ is prime (all computations ...
Saurabh Jain's user avatar
14 votes
3 answers
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 ...
user6245072's user avatar
14 votes
3 answers
1k 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 ...
Neil Slater's user avatar
14 votes
2 answers
954 views

What are the state-of-the-art algorithms for pathfinding on a continuous map of the Earth?

Suppose I have got a solar-powered autonomous surface vessel somewhere in the fjords of Norway, supplied with a fairly recent set of maps, a GPS receiver, and no means of downlinking detailed commands ...
Deer Hunter's user avatar
12 votes
3 answers
34k 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 ...
statBeginner's user avatar
12 votes
2 answers
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 ...
quant's user avatar
  • 253
12 votes
1 answer
6k 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: ...
jmad's user avatar
  • 9,498
11 votes
2 answers
4k 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 ...
Shahab_HK's user avatar
  • 147
11 votes
1 answer
10k views

Parallel algorithm for finding the maximum in $\log n$ time using $n / \log n$ processors

We were presented in class with an algorithm for finding the maximum in an array in parallel in $O(1)$ time complexity with $n^2$ computers. The algorithm was: Given an array A of length n: Make a ...
Gil's user avatar
  • 287
10 votes
1 answer
920 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-...
David Richerby's user avatar
10 votes
2 answers
248 views

Determining the particular number in $O(n)$ time and space (worst case)

$\newcommand\ldotd{\mathinner{..}}$Given that $A[1\ldotd n]$ are integers such that $0\le A[k]\le m$ for all $1\le k\le n$, and the occurrence of each number except a particular number in $A[1\ldotd n]...
Yai0Phah's user avatar
  • 621
9 votes
2 answers
19k views

Is search a binary heap operation?

According to the Wikipedia page, search is "not an operation" on binary heaps (see complexity box at top-right). Why not? Binary heaps may not be sorted, but they are ordered, and a full graph ...
Barry Fruitman's user avatar
9 votes
2 answers
10k views

How does the NegaScout algorithm work?

On Alpha-Beta pruning, NegaScout claims that it can accelerate the process by setting [Alpha,Beta] to [Alpha,Alpha-1]. I do not understand the whole process of NegaScout. How does it work? What is ...
sam's user avatar
  • 339
9 votes
1 answer
919 views

$O(\frac{\log n}{\log \log n})$ algorithm for the prefix parity problem

The prefix parity problem can be defined as follows. You are given a string $S$ of length $n$ and initially every character is $0$. Then you want to build a data structure that can support updates ...
jsguy's user avatar
  • 629
9 votes
5 answers
18k views

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

A gardener considers aesthetically appealing gardens in which the tops of sequential physical trees (eg palm trees) are always sequentially going up and down, that is: ...
Alan Evangelista's user avatar
9 votes
1 answer
5k 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, ...
gvdr's user avatar
  • 93
8 votes
3 answers
16k views

What is the difference between exhaustive search & combinatorial search?

I get used to think exhaustive search and combinatorial search are same, but I got confused by reading a paper! What is the difference between exhaustive search & combinatorial search ?
Mahdi Khosravi's user avatar
8 votes
4 answers
5k 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) ...
WHY's user avatar
  • 213
8 votes
1 answer
13k 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 ...
sema's user avatar
  • 183
7 votes
2 answers
577 views

Compression type that can be searched

Is there ANY compression type that can compress a file, and then that compressed file can be searched without uncompressing the file?
Albert Renshaw's user avatar
7 votes
3 answers
8k 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$...
Somnium's user avatar
  • 275
7 votes
1 answer
1k views

Why choose D* over Dijkstra?

I understand the basis of A* as being a derivative of Dijkstra, however, I recently found out about D*. From Wikipedia, I can understand the algorithm. What I do not understand is why I would use D* ...
user-2147482637's user avatar
7 votes
1 answer
833 views

Alpha-Beta Pruning with simultaneous moves?

I have a game I'm building some ai for that has 2 players making simultaneous moves. In this game there is exactly one move where, if they both make it at the same time, the outcome is different than ...
Fishtoaster's user avatar
7 votes
2 answers
2k 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 ...
Michael Wehar's user avatar
7 votes
3 answers
25k views

Artificial Intelligence: Condition for BFS being optimal

It is said in the book Artificial Intelligence: A Modern Approach for finding a solution on a tree using BFS that: breadth-first search is optimal if the path cost is a nondecreasing function of ...
Varaquilex's user avatar
7 votes
1 answer
2k views

nlp: phonetic edit distance between a word and the closest of a set of words

Let's say someone is using Dragon Dictation, Google Speech, or some other free form dictation software (it will recognize anything they say to the best of its ability). I have some reasonably large ...
Brent Allard's user avatar
7 votes
1 answer
7k views

Why do we prefer DFS to find connected components?

In finding the connected components in a graph, why do we use DFS, instead of BFS?
Hazem Alabiad's user avatar
7 votes
2 answers
185 views

A key-value datastructure with fast (on average) member move and nearest neighbors search?

I have a 3 dimensional float key search space (say a simulation world). I want to keep my values (ints, agent ids) in a data structure that can perform nearest neighbors search (with search for N ...
DuckQueen's user avatar
  • 201
7 votes
1 answer
1k 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 ...
JnBrymn's user avatar
  • 245
7 votes
1 answer
2k views

How does the Galil's rule work on Boyer-Moore algorithm?

I would like to know how Boyer-Moore text searching algorithm with Galil's rule works,. I tried to search for but I couldn't understand the information I found, for example this Wikipedia page. And ...
Andi Domi's user avatar
7 votes
0 answers
2k views

Stopping condition for goal-directed bidirectional search for shortest path

So I have a graph and need to find shortest path between two points in it. I need1 to do it it using bidirectional search. The bidirectional search should be goal-directed, i.e. A*. So let $l(u,v)$ ...
Jan Hudec's user avatar
  • 658
7 votes
1 answer
1k views

Find maximum in array without comparisons between elements

Suppose $A$ is an array of integers, $|A|=n$, $A=\{a_i|1\leq a_i\leq N, i=1\ldots n\}$. The goal is to find an efficient algorithm $\cal{F}$ to find maximum element in $A$ with these restrictions: ...
sas's user avatar
  • 201
6 votes
2 answers
7k 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 ...
user26288's user avatar
6 votes
2 answers
2k views

Expected number of updates of minimum

I came across the following problem in a exam. We choose a permutation of n elements $[1,n]$ uniformly at random. Now a variable MIN holds the minimum value seen so far at it is defined to $\infty$ ...
Phani Raj's user avatar
  • 163
6 votes
1 answer
463 views

Given an array of size N, if you know that all of the elements are white except for one, how to find the index of that element efficiently?

Yesterday while returning home, I walked past a house that had a camera. For some reason I started thinking about how these cameras work, and how you would use them in case of robbery. While thinking ...
jsguy's user avatar
  • 629
6 votes
1 answer
6k views

Algorithm to search substring in a circular string?

I need an algorithm to search for substrings. I checked different resources, and it seems that the most known algorithms are the Boyer–Moore and the Knuth–Morris–Pratt. However, as far as I ...
kebs's user avatar
  • 173
6 votes
1 answer
36k views

Given two heuristic values how do I tell which one is admissible?

I am given 2 list of admissible values for a graph, and the graph with the real cost to each of the nodes. Am I correct in thinking the way to see which one is admissible is add up all the values of ...
orange's user avatar
  • 197
6 votes
3 answers
15k views

Is uniform cost search optimal?

In my AI lecture notes (also many other AI lectures) it's written that uniform cost search is optimal (that is, uniform search always outputs the optimal path), but what if the cost is negative, won't ...
Logan's user avatar
  • 193
6 votes
2 answers
8k views

Where does the heuristic come from in the A-star algorithm and how do we know it has the right properties?

I am trying to understand some notes regarding the A-star algorithm. The example used is to show how the algorithm can be used as a (more efficient) alternative to Dijkstra's algorithm for finding ...
Clive Long's user avatar

1
2 3 4 5
14