Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [searching]

The tag has no usage guidance.

1
vote
0answers
20 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 (...
0
votes
0answers
10 views

How to use HITS algorithm in a web search engine?

I implemented the classical non-weighted converged version of HITS algorithm. I create a root set and a base set from the root set and then I applied the HITS algorithm and got the authorities and ...
0
votes
0answers
30 views

When to use which variant of the loop condition in binary search?

When solving a search problem with binary search, sometimes the loop condition is while low < hi and sometimes it is ...
1
vote
1answer
63 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. ...
1
vote
3answers
267 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 ...
1
vote
2answers
38 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 ...
3
votes
1answer
143 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 ...
1
vote
1answer
53 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 ...
0
votes
1answer
61 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 ...
2
votes
1answer
151 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 ...
1
vote
1answer
55 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,...
1
vote
1answer
40 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 ...
1
vote
1answer
65 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
1answer
144 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 ...
2
votes
2answers
686 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 ...
2
votes
2answers
230 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
1answer
223 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: ...
2
votes
2answers
182 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 ...
1
vote
3answers
116 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 ...
0
votes
1answer
41 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 ...
1
vote
1answer
54 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
1answer
69 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 ...
1
vote
2answers
56 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 ...
15
votes
9answers
3k 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)$ ...
0
votes
1answer
124 views

Finding longest prefix of a given string in set of strings that satisies 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 ...
1
vote
1answer
51 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 ...
4
votes
1answer
170 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 ...
2
votes
1answer
74 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. ...
1
vote
0answers
23 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 ...
1
vote
0answers
24 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 ...
1
vote
1answer
68 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 <...
0
votes
4answers
126 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 ...
1
vote
1answer
63 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 ...
4
votes
2answers
73 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
4answers
76 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 $...
3
votes
1answer
3k 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 ...
1
vote
1answer
75 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 ...
4
votes
1answer
242 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
0answers
32 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 ...
0
votes
1answer
110 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
votes
1answer
87 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? ...
7
votes
0answers
130 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 ...
3
votes
1answer
86 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 ...
4
votes
2answers
578 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. ...
2
votes
1answer
139 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 ...
6
votes
1answer
172 views

What other involutions are there besides xor?

There is a classic problem of finding the only number that occurs an odd number of times in a list. The solution is to xor everything and the result is the requested number. The key properties used ...
1
vote
1answer
40 views

Pick matrices such that each partial sum is positive

There is a sequence of $n$ sets, each set contains a constant number of constant-size vectors, e.g: $\{M_{1,1},M_{1,2},M_{1,3},M_{1,4}\}$ $\{M_{2,1},M_{2,2},M_{2,3},M_{2,4}\}$ ... $\{M_{n,1},M_{n,2},...
0
votes
0answers
245 views

Eggs and Floors Puzzle - Alternate

Recently I've run across the "Two eggs, 100 floors" problem: You are given two eggs, and access to a 100-story building. Both eggs are identical. The aim is to find out the highest floor from which ...
3
votes
1answer
278 views

How to tell if a Heuristic is monotonic

I've applied a Heuristic to a puzzle where I need to move all off the B's the the right of the W's. my Heuristic is the total distance of the B's from the right most W's. my initial state is (B,B,B,*,...
6
votes
2answers
1k views

Check if adding an edge to a DAG results in a cycle

On the begining: It is a programming contest problem, but not from on-going one. Unfortunatelly, I can't provide any link to this task, because it is not publically available. It was from one of the ...