Questions tagged [search-algorithms]

Algorithms for finding an element in some specified data-structure (most commonly, in a tree).

Filter by
Sorted by
Tagged with
1 vote
1 answer
37 views

A nearest neighbor data structure for meshes

I am trying to find a lightweight data structure to find the nearest neighbor mesh (a mesh being a collection of non-unique triangles) for a given point in R3 (3D Euclidean space). I have seen nearest ...
user avatar
  • 157
1 vote
0 answers
44 views

Search algorithm with at most a constant $k$ failed accesses [duplicate]

Let $A$ be an array sorted in non-increasing order. Let $m$ be a natural number. For example, let $m = 10$. We want to find the index $i$ such that $A[:i]$ contain elements less than or equal to $m$, ...
user avatar
0 votes
1 answer
79 views

Is there a hash-map implementation optimized to favor key lookups based on frequency (if key is referenced the most then it is searched first)?

I have started to play around with HTTP3 which relies on QUIC for transport. I have noticed that I very often have a finite number of Web Transport sessions stream data continuously along side burst-y ...
user avatar
1 vote
1 answer
19 views

Efficient search of a large set of documents to find documents that only contain a particular set of words

Say I have a set of documents $D = \{d_1, d_2, \dots, d_n\}$ in some natural language. Each document $d_i$ consists of a subset of words from a word pool $W = \{w_1, w_2, \dots, w_k\}$. For example, $\...
user avatar
1 vote
0 answers
28 views

Unusual version of a binary search algorithm

For one dimensional, continuous binary search most effective algorithm would remember boundaries. For example if boundaries are 0.7 and 0.9, point to check would be 0.8. And if result is 'too small', ...
user avatar
2 votes
0 answers
30 views

Understanding MTD-f

In the MTD-f algorithm: ...
user avatar
  • 123
2 votes
2 answers
523 views

How can I apply binary search to find two adjacent increasing elements in an unsorted array?

I need to write a function that gets an array of numbers $a$ as an input and returns an index $i$ such that $a[i]<a[i+1]$ if it exists, if such $i$ doesn't exist return $-1$. (return any index $i$ ...
user avatar
  • 164
3 votes
1 answer
25 views

optimal search algorithm for finding parameters and thresholds

I have the following problem: There are $n$ variables $x_i$, $i=1...n$, each can take integer values from 1 to $m$. For every set of values I can run a test which has a binary outcome ('Pass' or 'Fail'...
user avatar
2 votes
2 answers
117 views

Decision tree for searching element in sorted-array

Given the problem of having a sorted array $A$, an element $x$ to be searched for in the array $ A $, what is a lower-bound on the process of finding $x$ in $A$? The answer is $ \Omega(\log n) $ ...
user avatar
1 vote
1 answer
37 views

Complexity of Nelder-Mead Algorithms

If the objective function contains $n$ variables (e.g. $f(x_1, ..., x_n)$) in the Nelder-Mead algorithm (or other direct search methods), is there any known lower/upper bounds on how many times the ...
user avatar
0 votes
1 answer
41 views

O(Log n) Search - Array

So, there's a LeetCode problem that has you find a O(log n) solution to finding a target number in a rotated sorted array. As an example: ...
user avatar
-1 votes
1 answer
111 views

Is there an O(m (log n+ log m))-time algorithm that finds k-th smallest element in a row-wise-sorted two dimensional array?

I prepare for entrance exam and try to practice some hard problems. The following nice problem is problem 1(c) of this problem set. Suppose we are given a two-dimensional array $A[1...m][1...n]$ in ...
user avatar
  • 7
2 votes
1 answer
57 views

Research project problem on Computational Geometry

(Most fair region) Let $P$ be a set of $n$ points in the two-dimensional plane. Each point in $P$ is either colored red or blue. Given an axis-aligned rectangle $R_{ab}$ of size $a\times b$ , design ...
user avatar
4 votes
6 answers
2k views

"Guess the number" Problem on Turing machines

I am currently learning about the concept of Turing Machines and trying to relate it with my knowledge on the application of the Binary Search algorithm. The problem I am working on is to write an ...
user avatar
0 votes
0 answers
8 views

How to do contains-edit-distance match across many strings at once efficiently?

given these strings (one per line) oaccdefhmhhvoobagqhv gremqskkhhpipkbwlsgd jcfonoxymqhnkidrwhup gijquczafmhygjsiyqxe abdcegfcnxdmtqqjgpuc oayapipwinwuzdvcyaxm hfudoatjkjxpmztpseav ...
user avatar
2 votes
0 answers
21 views

Pairwise intersections of segments in a rectangle

Let V be a set of vertical segments, and H be a set of segments parallel to a line (e.g. a line with slope -1). We want to find a data structure for set S = V ∪ H to find all pairs (v,h) of segments ...
user avatar
2 votes
1 answer
33 views

How do distributed joins work in a distributed relational database system?

I have been looking around for a few days trying to find a clear and concise description of how, at a technical/implementation level, how distributed joins work, but haven't found much. The best so ...
user avatar
  • 1,871
0 votes
0 answers
44 views

Algorithm using a trie while calculating edit distance for fuzzy-string autocomplete matching?

In the paper Efficient Error-tolerant Query Autocompletion by Xiao et al., they state: The existing state-of-the-art solutions to the query autocompletion with edit distance constraints adopt the ...
user avatar
  • 1,871
0 votes
1 answer
41 views

How to evaluate all the binary sequences, generated from $2^{100}$ for finding all the sequeces which contain minimum $10$ zeros?

Suppose I have a set of $2^{n}$ number of binary sequences. And I have to select only those sequences which contain a minimum ${P}$ number of $0$ in it. For example, please consider the below one Eg. ...
user avatar
  • 168
0 votes
0 answers
6 views

how do I store 3D rectangle geometric data in kd-tree and check closeness?

There are a bunch of 3D rectangle and I plan to store them in KD-tree for neighborhood search. How to construct such tree and how to check if two rectangle are next to each other?
user avatar
1 vote
1 answer
53 views

what are good data structure algorithm for fast 3D coordinates search?

I want to form data structure for nearby neighbor search for 3D coordinates. What is the best way to do so?
user avatar
1 vote
1 answer
68 views

Find repeated patterns in a string via lossy compression

Description The task is to identify repeated patterns in a string and do lossy compression of the input string using the found patterns. The output is a list containing different ways of encoding the ...
user avatar
  • 113
1 vote
0 answers
138 views

Algorithm to find maximum sum over weighted overlapping intervals

Suppose we are given n open intervals $(a_1, b_1), ..., (a_n, b_n)$, with interval $i$ being assigned a weight $w_i$ for all $i$. Define a "good subset" of intervals to be a subset of those $...
user avatar
  • 121
1 vote
0 answers
638 views

Split the given array into K subsets such that maximum sum of all subsets is minimum

Given an array of $N$ elements, $A$, and a number $K$. ($1 \leq K \leq N$) . Partition the given array into $K$ subsets (they must cover all the elements but can be noncontiguous too). The maximum ...
user avatar
1 vote
1 answer
48 views

Examples of comparison-based algorithms that are not a sort or a search over lists

Can you share examples of comparison-based algorithms used in practice that are not a sort or a search over lists? Heapify is an example of a comparison-based algorithm that is neither a sort nor a ...
user avatar
  • 283
4 votes
0 answers
88 views

Searching a bitonic array with roughly $2\log n$ comparisons

I don't know how to search a bitonic array with roughly $2\log n$ comparisons in the worst case. What I am trying now is to find the maximum integer using roughly $\log n$ comparisons (binary search) —...
user avatar
  • 141
1 vote
1 answer
27 views

Can graphs have a serialized canonical form for the purpose of very fast graph structure look-up (subgraph isomorphism)?

Let suppose we order the nodes first by degree (in + out), to get a list of node structures: ...
user avatar
1 vote
1 answer
74 views

Design an optimal algorithm that finds 2 array indices in a sorted array such that $A [i] + A [j] = k$

Text: ...
user avatar
0 votes
1 answer
234 views

True/False: If v is a leaf in every spanning tree resulting from DFS(s), then v is a leaf in every spanning tree resulting from BFS(s)

Let $G = (V,E)$ be a connected undirected graph. Let $s \in V$ be a vertex in the graph. True/False: If $v$ is a leaf in every spanning tree resulting from DFS(s), then $v$ is a leaf in every spanning ...
user avatar
0 votes
0 answers
28 views

Data structure for incremental KNN (IKNN) search over high-dimensional vectors

I have a database $D$ of n-dimensional numerical vectors, and I want to do an incremental KNN (IKNN) search over the vectors in $D$. More precisely, given a query vector $v_q \in D$ I need to find $k$ ...
user avatar
2 votes
0 answers
74 views

Can A* with an inadmissible heuristic still be optimal?

It is clear to me that if some heuristic $h(x)$ is admissible, then $A^*$ is guaranteed to find a least-cost path. But is it also possible that $A^*$ is optimal if $h(x)$ is not admissible? In other ...
user avatar
  • 21
4 votes
0 answers
88 views

How do search engines implement fuzzy search?

Googling "large horse walks into house" also returns results that contain "large horse in a house" and "the house has large horses". How is Google able to return near-...
user avatar
0 votes
0 answers
47 views

In a connected graph, determine all nodes reachable with a "edge-simple" path from node A to node B

I'm asked to write an algorithm which determine all points which appear in a "edge-simple" path connecting node A and node B, i-e a path which doesn't go 2 times in the same edge, but it can ...
user avatar
0 votes
0 answers
220 views

Number of shortest paths between two nodes in undirected unweighted graph

I'm trying to devise a $O(|V| + |E|)$ algorithm to calculate number of shortest paths between $s$ and $f$ on a undirected, unweighted graph. Can someone please check my pseudo-code? Also, isn't $O(|V| ...
user avatar
  • 113
1 vote
1 answer
28 views

Is the first distance that gets assigned to a node in BFS always the shortest distance?

Consider the following bfs pseudo code that calculates distances of all nodes from $s$ in graph $G=(V,E)$. I know that if $G$ was undirected and unweighted, then the above bfs would calculate correct ...
user avatar
  • 113
1 vote
1 answer
93 views

Algorithm to find the path with minimum bending points on a square grid board

Let's suppose we have a square grid board like the one shown in the picture below: I'm wondering how I can find the path with minimum number of "bending" points (like the ones shown in red) ...
user avatar
0 votes
0 answers
25 views

Finding matches between an input string and a fixed set of strings

I need to compare an input string to multiple strings which I'll refer to as fixed strings, and you can assume the latter won't change. Comparison disregards letters with special characters, only ...
user avatar
  • 158
0 votes
0 answers
50 views

Finding the Solution out of N possibilities

Suppose there are 10 (4x4) matrices, where the elements in each matrix are dependent on one variable ($\theta$) non-linearly. All the matrices are independent of each other, so there are 10 $\theta$s (...
user avatar
0 votes
1 answer
48 views

In RBFS, why should expanded nodes inherit F-value of their parent, if their f-value (g(n)+h(n)) is less than their parent's F-value

Here https://uk.wikipedia.org/wiki/RBFS and here https://www.eecs.yorku.ca/course_archive/2013-14/F/3401/slides/15b-RBFS.pdf it's said that f[s] ← max(g(s)+h(s) , f[node] ) Why is it so? I can see a ...
user avatar
1 vote
0 answers
19 views

Does this Hamming-like algorithm for solving a permutation of an address space have a name?

I'm working on reverse engineering the bit stream format of an FPGA, in particular regarding the address translation of the BRAM (block RAM), but the algorithm could in general be used for any ...
user avatar
  • 111
0 votes
1 answer
43 views

Search algorithm for an expensive boolean function

I have the following problem. We have a boolean function $f$ that is expensive to compute for a given input. We need to find the smallest positive integer $n$ such that $f(n)$ is true. We don't know ...
user avatar
2 votes
1 answer
83 views

array empty cell search algorithm

I'm Telecommunication student so I don't have Computer Science background, just in case if my question looks stupid. Here is my scenario: Consider an empty array named ...
user avatar
1 vote
1 answer
44 views

How to search all possible combinations for a product?

I'm looking for the name of the problem stated below or, if available, even the algorithm to solve it. This is a hypothetical idea of mine, I don't actually have the necessary data to implement it. ...
user avatar
  • 111
0 votes
1 answer
45 views

Best algorithm for Decisional 4-XOR problem?

Decisional 4-XOR Problem: Assume $M>>n$ (e.g. $M=50n$ ). Let $A_1,A_2,A_3,A_4$ be sets consisting of $M$-bit elements. Each set has order exactly $2^n$. Decide whether or not there exists $a_i \...
user avatar
  • 11
1 vote
2 answers
63 views

Difference Between k-center and k-mean/median

I know that k-mean/median is to find a set $F$ that minimize $$\sum_{i\in C}\min_{j \in F} d(i,j)$$ Where $C$ is set of clients and $F$ set of facilities. (For k-mean you just square the distance). ...
user avatar
4 votes
0 answers
40 views

Using graph symmetries to speed up subgraph enumeration

I have an undirected graph $G$. It has some symmetries in the sense that I know it's automorphism group $\text{Aut}(G)$. I am searching for a specific subgraph defined by some constraints $\phi$ and ...
user avatar
1 vote
1 answer
38 views

Avoid Storing Keys in Key-Value Store by Replacing the Key with 128-bit Murmur3 Hash

I want to develop LRU key-value data store and in that wanted to get rid of space to store the key itself. Instead wanted to store a 128 bit murmur hash. The structure of data-store that I want to ...
user avatar
2 votes
0 answers
20 views

SMA*+: Usefulness of culling heuristics

The paper on SMA*+ proposes a very interesting idea of having a culling heuristic different from the full path cost estimation (so called $f$-cost). In the benchmark they use a culling heuristic equal ...
user avatar
  • 423
2 votes
0 answers
19 views

SMA*+: f-cost estimation of re-generated nodes

I was reading the paper on SMA*+, which is very interesting as it implements most improvements I thought of when reading the paper on SMA*. But I have 3 questions that I think are related to my ...
user avatar
  • 423
1 vote
1 answer
29 views

Is this a good way to arrange data in a tree?

I was recently learning about Binary Search Trees(BSTs) and thought it could be made even more efficient by making some changes. As binary search trees have numbers greater than the root node on the ...
user avatar

1
2 3 4 5
14