Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
31 votes
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 ...
Mario Cervera's user avatar
23 votes
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 ...
Taemyr's user avatar
  • 605
17 votes

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 ...
Tom van der Zanden's user avatar
17 votes
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 ...
John L.'s user avatar
  • 39k
16 votes

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: ...
Ilmari Karonen's user avatar
16 votes
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. ...
jbapple's user avatar
  • 3,380
15 votes

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 ...
reffu's user avatar
  • 411
14 votes

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 ...
MayankPratap's user avatar
14 votes

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 ...
Tobi Alafin's user avatar
  • 1,617
14 votes

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 ...
Steven's user avatar
  • 29.5k
11 votes

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", "...
Pål GD's user avatar
  • 16.4k
10 votes
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
Eugene's user avatar
  • 1,086
10 votes

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 ...
nosyarg's user avatar
  • 232
9 votes

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 ...
Shaull's user avatar
  • 17.2k
9 votes
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 ...
D.W.'s user avatar
  • 160k
9 votes
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 ...
Benny Profane's user avatar
9 votes

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

BFS is usually described something like the following (from Wikipedia). ...
David Richerby's user avatar
9 votes

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 ...
D.W.'s user avatar
  • 160k
8 votes

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. ...
SmallChess's user avatar
8 votes

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 ...
David Richerby's user avatar
7 votes
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 ...
Nitin's user avatar
  • 186
7 votes

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 ...
xdavidliu's user avatar
  • 858
7 votes
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 ...
Carlos Linares López's user avatar
7 votes
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 ...
Nat's user avatar
  • 1,351
7 votes
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-...
John L.'s user avatar
  • 39k
7 votes

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 ...
NaturalLogZ's user avatar
6 votes

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 ...
Tom van der Zanden's user avatar
6 votes

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$ ...
D.W.'s user avatar
  • 160k
6 votes
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 ...
Carlos Linares López's user avatar
6 votes

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

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 ...
Riley's user avatar
  • 280

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