The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Tag Info

Hot answers tagged search-algorithms

76

If you apply binary search, you have $$\log_2(n)+O(1)$$ many comparisons. If you apply ternary search, you have $$2 \cdot \log_3(n) + O(1)$$ many comparisons, as in each step, you need to perform 2 comparisons to cut the search space into three parts. Now if you do the math, you can observe that:  2 \cdot \log_3(n) + O(1) = 2 \cdot \frac{\log(2)}{\log(3)}...

43

I'd like to quote an answer from Stack Overflow by hstoerr which covers the problem nicely: That heavily depends on the structure of the search tree and the number and location of solutions. If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better. If the tree is very deep and solutions are rare, depth ...

37

One point that's important in our multicore world: BFS is much more easy to parallelize. This is intuitively reasonable (send off threads for each child) and can be proven to be so as well. So if you have a scenario where you can make use of parallelism, then BFS is the way to go.

31

(I made this a community wiki. Please feel free to edit.) If $b$ is the branching factor $d$ is the depth where the solution is $h$ is the height of the tree (so, $d\le h$) Then DFS takes $O(b^h)$ time and $O(h)$ space BFS takes $O(b^d)$ time and $O(b^d)$ space IDDFS takes $O(b^d)$ time and $O(d)$ space Reasons to choose DFS must see whole tree anyway ...

31

I see four main ways to solve this problem, with different running times: $O(n^2)$ solution: this would be the solution that you propose. Note that, since the arrays are unsorted, deletion takes linear time. You carry out $n$ deletions; therefore, this algorithm takes quadratic time. $O(n \: log \: n)$ solution: sort the arrays beforehand; then, perform a ...

26

DCTLib is right, but forget the math for a second. By your logic then, n-ary should be the fastest. But if you think about it, n-ary is exactly equal to a regular iteration search (just iterating through the list 1 by 1, but in reverse order). First you select the last (or next to last) item in the list and compare that value to your comparison value. Then ...

24

When doing a DFS, any node is in one of three states - before being visited, during recursively visiting its descendants, and after all its descendants have been visited (returning to its parent, i.e., wrap-up phase). The three colors correspond to each of the three states. One of the reasons for mentioning colors and time of visit and return is to ...

22

I would not call this a binary search. It is clearly similar to binary search and it's natural to see it as a refinement of binary search. However it has significantly different algorithm complexity characteristics, Interpolation Search has expected run time of O(log(log(n)) assuming the data is uniformly distributed, however it pays for this by having O(n)...

20

This problem is known as the “minimum common string partition problem.” (More precisely, the answer in the minimum common string partition problem equals the answer in your problem plus 1.) Unfortunately, it is NP-hard, even with the restriction that each letter occurs at most twice in each of the input strings, as is proved by Goldstein, Kilman, and Zheng ...

19

If the edges in the graph only represent valid moves between certain positions, using Dijkstra's would work just fine. However as the graph is unweighted it would be overkill. A simple breadth-first-search will give the optimal answer.

19

This is called rendezvous problem. As the paper: Mobile Agent Rendezvous: A Survey mentioned, this problem is original proposed by Alpern: The Rendezvous Search Problem: Two astronauts land on a spherical body that is much larger than the detection radius (within which they can see each other). The body does not have fixed orientation in space, nor ...

17

One scenario (other than finding the shortest path, which has already been mentioned) where you may have to choose one over the other to get a correct program would be infinite graphs: If we consider for example a tree where each node has a finite number of children, but the height of the tree is infinite, DFS might never find the node you're looking for - ...

17

A* maintains a priority queue of options that it's considering, ordered by how good they might be. It keeps searching until it finds a route to the goal that's so good that none of the other options could possibly make it better. How good an alternative might be is based on the heuristic and on actual costs found in the search so far. If the heuristic ...

16

Yes, this is known as Interpolation Search. With some caveats (depending on your computational model and the distribution of the data) its expected running time is $O(\log \log n)$, better than binary search.

16

The $\Theta(n)$ difference-of-sums solution proposed by Tobi and Mario can in fact be generalized to any other data type for which we can define a (constant-time) binary operation $\oplus$ that is: total, such that for any values $a$ and $b$, $a \oplus b$ is defined and of the same type (or at least of some appropriate supertype of it, for which the ...

16

Create a buffer of size $2k$. Read in $2k$ elements from the array. Use a linear-time selection algorithm to partition the buffer so that the $k$ smallest elements are first; this takes $O(k)$ time. Now read in another $k$ items from your array into the buffer, replacing the $k$ largest items in the buffer, partition the buffer as before, and repeat. This ...

15

Breadth-first and depth-first certainly have the same worst-case behaviour (the desired node is the last one found). I suspect this is also true for averave-case if you don't have information about your graphs. One nice bonus of breadth-first search is that it finds shortest paths (in the sense of fewest edges) which may or may not be of interest. If your ...

15

Think of it like this. You have a problem, with input $x$ and you know how to verify a solution if you ever found one (like the inverse of a matrix or whatever you'd like to imagine). Now, take your favourite programming language (say Python), and create every single Python program consisting of at most 10 characters! Then you run all those programs with ...

15

Element = Sum(Array2) - Sum(Array1) I sincerely doubt this is the most optimum algorithm. But it's another way to solve the problem, and is the simplest way to solve it. Hope it helps. If the number of added elements is more than one, this won't work. My answer has the same run time complexity for best, worst, and average case, EDIT After some thinking, ...

14

I'd post this as a comment on Tobi's answer, but I don't have the reputation yet. As an alternative to calculating the sum of each list (especially if they are large lists or contain very large numbers that might overflow your data type when summed) you can use xor instead. Just calculate the xor-sum (i.e. x^x^x...x[n]) of each list and then xor ...

13

Nicholas already provided a perfect answer. However, let me address your original attempt to use depth-first search. First, either Dijkstra (which works fine with unweighted nodes as noted by Nicholas Mancuso) or breadth-first search incur in exponential waste of your memory. Their advantage, however, is that they never re-expand any nodes while they are ...

12

Compressed self-indexes such as the FM Index allow arbitrary substring searches in near entropy-compressed space. These are essentially compressed suffix arrays or suffix trees, which have a lot of literature. Basic substring search can be o(k) or o(k log n) in time for length k, depending on what data structures are chosen (different types of rank/...

11

If the heuristic function is not admissible, than we can have an estimation that is bigger than the actual path cost from some node to a goal node. If this higher path cost estimation is on the least cost path (that we are searching for), the algorithm will not explore it and it may find another (not least cost) path to the goal. Look at this simple example....

10

Actually it depends on your point of view, or level of detail. The heap, or better priority queue, as abstract data structure usually supports operations like is-empty, add-element, delete-min. And usually not find-element. This is the data structure seen as a specification, fixing the set of operations and their behaviour. The implementation is unknown, it ...

10

If the elements need not be distinct, then you cannot have an $O(\log n)$ time algorithm. Consider the sorted array $[0,0, \dots, 1]$ which has been cyclic shifted $k$ (unknown) times and you need to find where the $1$ appears. This needs $\Omega(n)$ time, as you need to examine at least $n-1$ elements. However, if you assume the elements are distinct, ...

10

My two cents: exhaustive search is also known as brute force search, an approach in which you have no better strategy than to explore the entire search space, testing every possible candidate solution. Two examples were given by @Yuval Filmus. If you are really unlucky, the solution may well be the last candidate explored, or one of the last ones. Therefore, ...

10

All parts of proving the claim hinge on 2 crucial properties of trees with undirected edges: 1-connectedness (ie. between any 2 nodes in a tree there is exactly one path) any node can serve as the root of the tree. Choose an arbitrary tree node $s$. Assume $u, v \in V(G)$ are nodes with $d(u,v) = diam(G)$. Assume further that the algorithm finds a node $x$ ...

10

Warmup: random bitvectors As a warm-up, we can start with the case where each bitvector is chosen iid uniformly at random. Then it turns out that the problem can be solved in $O(n^{1.6} \min(k, \lg n))$ time (more precisely, the $1.6$ can be replaced with $\lg 3$). We'll consider the following two-set variant of the problem: Given sets $S,T \subseteq \{0,... 10 For your problem with the array: No, there is no better algorithm. That's the best you can do. Any deterministic algorithm will in the worst case have to look at every array element (technically: at least$n-1$of the$n$elements). This can be proven by an adversarial algorithm: consider any algorithm, and imagine it has looked at$n-2\$ elements and hasn'...

10

Use selection algorithm for linear time https://en.m.wikipedia.org/wiki/Selection_algorithm

Only top voted, non community-wiki answers of a minimum length are eligible