2022 Developer Survey is open! Take survey.

Questions tagged [searching]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
56 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 ...
user avatar
0 votes
0 answers
24 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 ...
user avatar
1 vote
1 answer
43 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 ...
user avatar
  • 111
0 votes
1 answer
95 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 ...
user avatar
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 ...
user avatar
2 votes
1 answer
723 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 ...
user avatar
1 vote
0 answers
49 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 (...
user avatar
  • 11
1 vote
1 answer
829 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. ...
user avatar
  • 645
3 votes
4 answers
4k 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 ...
user avatar
1 vote
2 answers
329 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 ...
user avatar
3 votes
1 answer
1k 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 ...
user avatar
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 ...
user avatar
  • 119
0 votes
1 answer
685 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 ...
user avatar
2 votes
1 answer
430 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 ...
user avatar
1 vote
1 answer
73 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,...
user avatar
1 vote
1 answer
112 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 ...
user avatar
  • 113
1 vote
1 answer
114 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 ...
user avatar
1 vote
1 answer
370 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 ...
user avatar
  • 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 ...
user avatar
2 votes
2 answers
579 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: ...
user avatar
0 votes
1 answer
557 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: ...
user avatar
  • 135
2 votes
2 answers
755 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 ...
user avatar
  • 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 ...
user avatar
0 votes
1 answer
46 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 ...
user avatar
  • 101
1 vote
1 answer
63 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$ ...
user avatar
0 votes
1 answer
96 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 ...
user avatar
1 vote
2 answers
75 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 ...
user avatar
  • 1,398
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)$ ...
user avatar
  • 275
0 votes
1 answer
247 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 ...
user avatar
  • 111
1 vote
1 answer
218 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 ...
user avatar
4 votes
1 answer
696 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 ...
user avatar
  • 41
2 votes
1 answer
237 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. ...
user avatar
  • 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 ...
user avatar
1 vote
0 answers
29 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 ...
user avatar
  • 168
1 vote
1 answer
86 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 <...
user avatar
  • 109
0 votes
4 answers
275 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 ...
user avatar
  • 109
1 vote
1 answer
83 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 ...
user avatar
  • 1,127
3 votes
2 answers
646 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 ...
user avatar
1 vote
4 answers
136 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 $...
user avatar
4 votes
1 answer
13k 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 ...
user avatar
0 votes
1 answer
243 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 ...
user avatar
  • 151
4 votes
1 answer
675 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 ...
user avatar
1 vote
0 answers
41 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 ...
user avatar
  • 111
0 votes
1 answer
520 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 ...
user avatar
  • 1,243
-1 votes
1 answer
233 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? ...
user avatar
  • 517
6 votes
0 answers
162 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 ...
user avatar
2 votes
1 answer
113 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 ...
user avatar
  • 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. ...
user avatar
1 vote
1 answer
146 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 ...
user avatar
6 votes
1 answer
203 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 ...
user avatar
  • 508