New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

# Tag Info

Accepted

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

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 ...
• 3,704
Accepted

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

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 ...
• 605

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

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 ...
• 13.3k
Accepted

### "Guess the number" Problem on Turing machines

Yes, it is pointless and absurd to implement an algorithm to "guess the number" using the most common kind of Turing machine, whose head can read any cell on the tape, since, as you pointed ...
• 39k

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

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: ...
• 2,160
Accepted

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

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. ...
• 3,380

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

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 ...
• 411

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

The intuition behind is very easy to understand. Suppose I have to find longest path that exists between any two nodes in the given tree. After drawing some diagrams we can observe that the longest ...
• 305

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

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 ...
• 1,617

### Time Complexity of Linear Search vs Brute Force

Time complexity is expressed as a function of some parameter, which is usually the size of the input. The combination lock is not a perfect analogy as it is not immediately clear what the input would ...
• 29.5k

### Why are search problems assumed to have the structure of "find a path in a graph"?

You are completely right: The problems we call search problems are typically problems that can be modeled as a graph problem. The general gist of it is that there are "states", "...
• 16.4k
Accepted

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

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

### What is the name of this search algorithm?

I do not think there is a name for that particular algorithm, but I think it will achieve similar performance to much simpler parallel algorithms for this task. In general when designing parallel ...
• 232

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

You can find the shortest cycle that contains $v$ by running BFS from $v$, and stopping at the first time that $v$ is reached again (or if BFS terminated without reaching $v$). An important property ...
• 17.2k
Accepted

### Why is the running time for BFS $O(b^{d+1})$?

This represents a difference between the kinds of problems the CS algorithms community usually uses BFS to solve, vs the kinds of problems the CS artificial intelligence community usually uses BFS to ...
• 160k
Accepted

### How binary search works in real world scenario?

As Prof. Filmus said, it isn't necessary for Binary Search Trees (hereafter referred to as BST's) to necessarily have ints/Integers as the data within the nodes. At least in Java, all we need is data ...

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

BFS is usually described something like the following (from Wikipedia). ...
• 81.8k

### Why are search problems assumed to have the structure of "find a path in a graph"?

There are at least two meanings of the word "search problem". In one context, we use the phrase "search problem" to refer to searching for paths in a graph, or making a sequence of ...
• 160k

### How does the NegaScout algorithm work?

NegaScout is a very simple algorithm. To understand we should first review iterative deepening negamax (minimax). Iterative deepening is a technique to search for depth i, then i+1, then i+2, etc. ...
• 191

### Why is the running time for BFS $O(b^{d+1})$?

The bounds $O(|V|+|E|)$ and $O(b^d)$ are talking about different things. The former is appropriate when you know what $V$ and $E$ are in advance, and they're both finite. The latter is ...
• 81.8k
Accepted

### Proof of correctness of A star search algorithm

Check the original paper which talks about its correctness - Hart, Peter E., Nils J. Nilsson, and Bertram Raphael. "A formal basis for the heuristic determination of minimum cost paths." Systems ...
• 186

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

Update 3 and corrected answer There's an error in the linked solution set (see update 2 below), but it can be easily corrected with @Yuval Filmus's suggestion in the question's comment, which further ...
• 858
Accepted

### Bidirectional Dijkstra vs Dijkstra

Absolutely yes! your arguments are correct. And, as matter of fact, it is very easy to come up with a graph where Bidirectional Dijkstra would expand more nodes than Unidirectional Dijkstra, following ...
• 3,463
Accepted

### 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) Kinda. While it's true that the ...
• 1,351
Accepted

### Search a sorted array that ends with zeros in O(log n) time

Here is a simple algorithm to solve the problem as in Yuval's comment. Algorithm Input: A positive number $w$ and array $A$ of $m$ numbers, $A[0],\cdots, A[m-1]$. The first $n$ numbers of $A$ are non-...
• 39k

### Time Complexity of Linear Search vs Brute Force

You are absolutely right that they are the same algorithm! At least, in this context. "Brute-force attack" is a general term referring to finding a solution to the problem at hand by trying ...
• 651

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

Interleaving two algorithms to get the best of both worlds is a known technique, though it is usually stated as running them in "parallel" and returning an answer as soon as either terminates. Though ...
• 13.3k

### Finding a value in a sorted array in log R time, R is the number of distinct elements

There is no such algorithm. Here's an information-theoretic proof that it can't be done, inspired by gnasher79's answer. Let's focus on the special case where $R=3$. Suppose there is a constant $c$ ...
• 160k
Accepted

### Are depth-first/breadth-first considered special cases of best-first?

The answer to your question is, in both cases, No. The reason is as follows: Both depth-first search and breadth-first search are uninformed search algorithms. A distinctive feature of these ...
• 3,463
You could append all of the $n$ strings together, and add an arbitrary character '\\$' not in the pattern to separate them. Then you could apply the Z algorithm on your original pattern and this new ...