Questions tagged [searching]
The searching tag has no usage guidance.
78
questions
1
vote
0
answers
39
views
Is there a comprehensive list of searching algorithms for sorted (and possibly unsorted) arrays available anywhere?
Classic searching algorithms such as binary searching and dictionary searching search sorted arrays based on a given element and make estimations on their own. What I'm looking for is a list of more ...
- 11
0
votes
1
answer
141
views
Return indices in the two sum problem
Given an array unsorted P of integers and a number m. I am trying to write a code that returns indices ...
- 138
0
votes
0
answers
25
views
Algorithm to find roots of a "bidimensional function"
The object I am studying is a bit more complicated than a bidimensional function, but I think I can explain what I need better with a simplified example. I can provide more details if asked.
So ...
- 101
1
vote
1
answer
101
views
Algorithm to find approximate position of element from a noisy sorted list
Let's have a static function f(n) which for a given n returns only these answers "lower" or "higher" comparing against an imaginary number x
In a sorted list ...
- 111
0
votes
1
answer
107
views
Databases and B-Trees: What are Keys and how are they related
I confused about the description & definition of "key" occuring as terminology for databases and b-trees.
In first case dealing with theory of databases a key is defined as a choice for ...
- 223
0
votes
2
answers
1k
views
minimum moves for Knight on a infinite chessboard [duplicate]
You are given an infinite chessboard, a knight, a source and a destination.(Normal chess rules apply) we are required to get move knight from source to destination in minimum moves possible.
I can ...
3
votes
1
answer
1k
views
In which situation do we choose randomized binary search instead of the normal binary search?
Both randomized and normal binary search takes O(log n) time complexity but why does the randomized version exist? In other words what is the advantage of randomized binary search even if it has same ...
- 65
1
vote
0
answers
59
views
Efficient data structure for multidimensional searching on intervals and keys
I am searching for a data structure that can capture a database, which is consisted of one column of intervals (like [0, 2], [4, 6]) and one/two columns of keys (...
- 11
1
vote
1
answer
1k
views
Proving correctness of search algorithms
I've seen correctness proofs for other searching algorithms; however, for this particular algorithm: search in a row-wise and column wise sorted matrix, I'm not able to generate a proper proof.
...
user40759
3
votes
4
answers
5k
views
Chess Knight minimum moves to destination on an infinite board
There are tones of solutions for Knights tour or shortest path for Knights movement from source cell to destination cell. most of the solutions are using BFS which seems the best algorithm.
Here is ...
- 268
1
vote
2
answers
361
views
Array contains elements that differ by K correctness proof
I have been puzzling over an algorithm that decides whether a sorted array of numbers contains two numbers that differ by k. I do not intuitively understand why ...
- 121
3
votes
1
answer
2k
views
Average-case complexity of linear search where half of the elements in the array are duplicates
I know that for an array of size n distinct elements, the Average Case complexity for linear search is as follows:
A(n) = $\frac{n + 1}{2}$
However, I am having trouble coming up with the Average ...
- 33
1
vote
1
answer
1k
views
Understanding Binary Search for Kth Smallest element in an Array
The Answer here shows a way to solve the problem with O(1) space. The approach uses Binary Search. I am finding really hard to wrap my head around why it works. I get why we did low + (high-low)/2 ...
- 119
0
votes
1
answer
936
views
Consistent heuristic and A*
The following graph has consistent heuristic.
An A* algorithm will alter its first guess ACD to the correct shortest path ABD... if it has consistent heuristic, doesnt it mean, that AB should be ...
- 1
2
votes
1
answer
498
views
A* 8-puzzle problem worst case memory usage
We are testing the A* algorithm with Hamming and Manhattan on the 8-puzzle (and its natural generalization n-puzzle) problem.
We have to answer the following question but I can't figure out what it ...
- 21
1
vote
1
answer
83
views
Number of elements with lower index equal to some element, for all items on an array
Let $A$ be an array of size $n$, and $f(i, r, a_r)$ be the number of indices $k$ such that $a_k$ = $a_r$ and $i \le k \le r$.
Example to clarify:
Imagine the array: $[1, 2, 3, 2, 2, 3, 4, 5]$. $f(0,...
- 209
1
vote
1
answer
121
views
Data-structure for dynamic disjoint-sets
I have a collection of objects, with certain properties (let say 3 - zone, type, owner) only having a small predetermined possible set of values (like enum).
This is just a simple (javascript) array ...
- 113
1
vote
1
answer
121
views
Computing min and max using median of 3 elements
How can I write an O(n)-time algorithm to find the minimum and maximum, given a list of n elements drawn from a totally ordered set using the subroutine median3(x,y,z) which returns the index of ...
1
vote
1
answer
410
views
return all strings contains given string in suffix tree
Here is my question:
Given a compressed suffix tree of string S and a substring T.
I need to return all substrings of S that begins with the substring T
sorted by lexicographic order.
My approach:
I ...
- 135
2
votes
2
answers
2k
views
Can we apply binary search for finding key 'x' in unsorted array?
Suppose we are given A, an array of size n, comprised of an increasing sequence of numbers followed immediately by a decreasing one. What is worst case time complexity of optimal algorithm to ...
user82290
2
votes
2
answers
685
views
Finding the shortest sublist that contains all search terms
I've been trying to get better at writing algorithms and came across a problem that was something like this:
Given a list of words:
...
0
votes
1
answer
644
views
return a key of a node with maximum value within a range of keys in B+ tree
I've been asked a question about B+ Tree.
The question is: Suppose we have object of the following type:
...
- 135
2
votes
2
answers
823
views
Find cut vertex in tree with constraint on the size of largest component
I have a connected and undirected graph without cycles (i.e. a tree), and I am trying to find a single cut vertex that, when removed, disconnects the graph into a set of connected components. The ...
- 25
1
vote
3
answers
130
views
Finding one of 2/3 of all array elements in constant expected time
How do I go about designing a constant time algorithm which satisfies the following I/O requirements:
Input: an array $A$ of length $3n$, containing $2n$ values of the symbol $X$ and $n$ of the ...
- 185
0
votes
1
answer
57
views
Search string excluding longer string containing substring that contains string, not exclusively longer string [closed]
How you define a search of text to find a string A, but exclude results that contains B only (which contains A), but not the both string A and string B?
For example:
String A : "Great Wall"
String B ...
- 101
1
vote
1
answer
66
views
Best complexity to find solutions to $x^2+y^2=z^2$
What is the algorithm with the best complexity that finds solutions in a given range to the equation $x^2+y^2=z^2$ ?
The best i could do is to iterate through all $x$ and all $y$ and store $x^2+y^2$ ...
0
votes
1
answer
103
views
Find multiple duplicates in $n$ size data set in linear time
Problem:
Given a vectors of size $n$ with integer data within $[1, n-1]$ range, find $if$ and $which$ numbers are multiple duplicates (numbers appearing more than once). The time complexity ought ...
- 293
1
vote
2
answers
101
views
Find all pairs (i, j), such that i + (i+1) + (i+2) + ... + j = n
We have give positive integer $n$, and we want to find all the pairs $(i, j), i\leq j$ such that: $$i + (i+1) +(i+2)+(i+3)+ \dots + j = n$$
Clearly we can try all possible pairs in $O(N^2)$, but that ...
- 1,408
15
votes
9
answers
4k
views
How to find 5 repeated values in O(n) time?
Suppose you have an array of size $n \geq 6$ containing integers from $1$ to $n − 5$, inclusive, with exactly five repeated. I need to propose an algorithm that can find the repeated numbers in $O(n)$ ...
- 275
0
votes
1
answer
273
views
Finding longest prefix of a given string in set of strings that satisfies some property
I have a set of strings, lets call them RULES. I have a function F which given 2 strings deterministically returns boolean value. Given one string, lets call it QUERY, what is the fastest way to find ...
- 111
1
vote
1
answer
235
views
Are divide and conquer searches applicable to unimodal decision problems?
Given a sorted list of booleans with consecutive 0s followed by consecutive 1s such as [0,0,0,0,1,1,1], binary search is able to find the first 1 after all the 0s in log(n) time.
Is this technique ...
user23893
4
votes
1
answer
894
views
Comparing A* search to Simulated Annealing
Good Afternoon,
I am comparing A* search to Simulated Annealing for an assignment, mainly the algorithms, memory complexity, choice of next actions, and optimality. Now, I am not 100% sure about my ...
- 41
2
votes
1
answer
277
views
range / interval query algorithm
I've an hash (base 32 for what it's worth):
hash = 'ab352eghjhngd4'
And I've subscribers that want to listen to new hashes in a range.
...
- 123
1
vote
0
answers
25
views
How may I look for 'regions' of text in a larger corpus of different texts
I have an extremely large (100GB+) corpus of many different texts. All of them are in English and 'well' formatted. They are not loaded into any kind of database, think of them as a huge collection of ...
- 121
1
vote
0
answers
32
views
Testing whether a set of integers can be written as a combination of module basis elements
Input
We are given a set of basis elements, $\ v_1$,$\ v_2$ ,...,$\ v_n$ of a $\mathbb Z^m$- module and a multiset of integers $\ B :=$ {$\ b_1, ..., b_m$}
Desired Output
Return true if there ...
- 168
1
vote
1
answer
90
views
Movement on Labyrinth with Best First Search
I have the following labyrinth where R is the robot(the parent node), red blocks are the obstacles where the R cannot move and <...
- 119
0
votes
4
answers
293
views
Check if I have a phone number [closed]
I was recently in an interview and was asked what would be the smallest memory foot print and fastest system to check if a given phone number is in your data store given that all phone numbers will ...
- 109
1
vote
1
answer
90
views
Open question regarding the DFS
It is an open question that whether $\mathsf{DFS\text{}}$ can be done in $O(m+n)$ time and $O(n)$ bits of space, where $n,m$ represent the number of vertices and edges in a undirected graph. see this ...
- 1,157
3
votes
2
answers
931
views
Graphs: Dectect a sink in $\mathcal{O}(V)$
Given a directed conected graph which representation is its adjacency matrix $A$, design an algorithm to detect a sink in $\mathcal{O}(V)$ time, being $V$ the number of vertices.
As definitions can ...
1
vote
4
answers
179
views
Locate all locations in a sorted array where arr[i]<arr[i+1]
Suppose you are given an array of $n$ integers with duplicates in non-decreasing order. The goal is to find the locations where a value is different from its neighbor.
For example, given the array $...
- 31
4
votes
1
answer
14k
views
How to prove that average complexity is N/2 for linear search in the unsorted array [duplicate]
All tutorials on algorithms show the complexity for the linear search in the unsorted array in the average case as N/2. I understand that the average case means the ...
- 315
0
votes
1
answer
281
views
Reference/book recommendations for search data structure
I am interested in data structures that support efficient searching of various kinds.
When I read the Wikipedia page of "search data structure", it says "Useful search data structures allow faster ...
- 151
4
votes
1
answer
811
views
Does this A-Star heuristic already exist?
I've been thinking about the A* algorithm recently. For context, A* is a graph-navigating algorithm most often used to solve problems that go "What is the shortest path from point A to point B?". It's ...
1
vote
0
answers
42
views
Is there a "diminishing returns" tree search algorithm?
I'm looking for an algorithm that will let me plug in a heuristic for scoring a subtree, and as the algorithm does a depth-first search, it stops when the score has:
Already hit a threshold (minimum ...
- 111
0
votes
1
answer
735
views
Print the number of subarrays of an array having negative sums
Problem statement: Given an array of N integers, find its number of negative subarrays (i.e sub arrays having negative summation). E.g: for an array $[1,-2, 4, -5, 1]$ there are 9 subarrays whose sum ...
- 1,283
-1
votes
1
answer
298
views
How to find a pair of array elements whose difference is smaller than the average difference?
How to find a pair of indices $1\le i \le n$,$1\le j \le n$, $i\neq j$ in array $A[1..n]$ such that $0\le A[i]-A[j]\le\frac{max(A)-min(A)}{n-1}$ in $\Theta(n)$ time? ...
- 527
6
votes
0
answers
164
views
When does greediness guarantee optimality?
I was wondering if there is any theoretical results characterizing under what condition does greedy algorithm actually finds the optimal solution.
Here is a motivating example. Suppose you are trying ...
- 61
2
votes
1
answer
131
views
Approximate Similarity Search
I am implementing an approximate similarity search using multi-index hashing. I have a set (T) of millions of strings (of same length) and I have a query string(P) (or set of strings) that needs to ...
- 23
3
votes
3
answers
2k
views
Why does linear search have $\frac{n}{2}$ comparisons on average?
I'm reading the Wikipedia page on Linear Search and it is mentioned that there are on average $\frac{n}{2}$ comparisons.
I tried working this out on my own.
First I considered the number of cases. ...
- 155
1
vote
1
answer
147
views
Minimize longest continuous streak of $1$s after flipping $m$ $-1$s to $1$s
Given an array a of length n of $-1$s and $1$s, and another input $m$, I was supposed to minimize the longest continuous streak of $1$s or $-1$s after flipping $m$ $-1$s to $1$s or vice versa.
I know ...
- 39