# Questions tagged [search-algorithms]

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

693 questions
Filter by
Sorted by
Tagged with
22 views

### Manhattan distance always less node expansion than misplaced tiles heuristic?

I created a 8-puzzle search solver using BFS, A* with manhattan distance, and A* with misplaced tiles. I generated data that said that for a particular random board, misplaced tiles did less node ...
29 views

### Time complexity of search algorithms?

Can we prove that classical search algorithms cannot do better than a binary search algorithm with complexity $O(log(n))$ ? If so, how do we prove it?
3k views

### Time Complexity of Linear Search vs Brute Force

I am currently watching the FreeCodeCamp Algorithms and Data Structures Tutorial. In the explanation for exponential time complexity, they explain that using a brute force attack on a combination lock ...
81 views

### Any text similarity algorithms for substrings?

I need to implement simple search on Python package names and I'm struggling with ranking the results. Considered Levenshtein distance, but it would give too low ranking for matches which contain the ...
1 vote
68 views

164 views

### Why is this proof that CHESS is in EXPTIME correct?

I've been reading the following paper (open) by Fraenkel and Lichtenstein that shows that the Generalized $n \times n$ Chess problem ($\texttt{CHESS}$) is $\texttt{EXPTIME-complete}$. They start by ...
111 views

### Find the largest caterpillar subtree

I have a problem to solve, but I am having some issues with it... Find an algorithm with time complexity O(V+E), where V and E stand for vertices and edges respectively. The algorithm searches a tree ...
39 views

### Performing fuzzy search queries on a large database of strings

I have a large database of strings (~10 million) I need to perform fuzzy search queries which would find the best match inside that database. The best match meaning the one that has the highest 'score'...
59 views

### What is the difference between Local Beam Search and Stochastic Beam Search?

I know that both of them select K randomly, and then choose the best K, as I understand the ... 1 vote
156 views

### Finding Optimal Configuration of Formula without trying every Permutation

I have a math problem I need to solve so I can complete an optimisation in a computer program. My initial approach was just to brute force all the possible permutations but it got out of hand quite ...
1 vote
122 views

### Perfect ordered hash function on ordered sequence

I have a sequence of integer tuples $t_1, t_2,..., t_N$ of different sizes in lexicographic order, e.g.: $(1, 1), (1, 2), (1, 3, 5), (1, 3, 6), (1, 5), (3), (3, 2, 3), (3, 7), (3, 8, 1), ...$ ...
31 views

### CPU limit for bitap algorithm bitmask

We have bitap (shift OR) algorithm that searches for a substring in a text. Bitap algorithm uses bit masks, so that it can perform bitwise operations very fast with the help of CPU. For example: ...
1 vote
370 views

### Ordered sequence with logarithmic insert and remove

Problem: we have a sequence of numeric values, e.g. [102, 25, 77, 17, 2, 13]. We need to implement 3 operations, each can be at most logarithmic time complexity. <...
89 views

71 views

### How is this "pathmax modification," $f(n^\prime) = \max(g(n^\prime) + h(n^\prime), f(n))$, useful?

I am studying the concept of heuristics in search algorithms, and the $A^*$ search algorithm in particular. I am told the following: Greedy search minimises estimated path-cost to goal. But it's ...
75 views

### How do these search algorithm diagrams work? How am I supposed to interpret them? And what algorithms do those last three represent?

I was shown these diagrams in the context of search algorithms. The green tile shows the initial state, and the orange tile shows the goal state. I am told that each option shows a path each search ...
1 vote
51 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 ...
30 views

### Hill climbing method searching special polynomial equations

I have system of two polynomial two variables, second order; monomials are {${1,x,y,x^2,xy,y^2}$} I want find special systems of polynomials: two or more roots in specified range, two root close to ...
8 views

### Optimising for many points in a monotone function

I'm trying to optimise (to a certain precision) a monotonic function for many points (100+). I know a-priori that the function is continuous, with some parts zero derivative. I know that all points ...
1 vote
118 views

I was told that search algorithm such as IDA* or Beam Search with any inadmissible heuristic is not guaranteed to find a solution. Can someone explain why that is the case? I was thinking sure the ...
34 views

### Iterative algorithm for assembly index? [duplicate]

DOI: 10.3390/e24070884 provides pseudocode for computing the assembly index of an object. It is written as recursive algorithm, which might be fine. But I would like to implement an iterative version ...
1 vote
66 views

### Search for largest element in 1st monotonic subarray with an array consisting of 3 monotonic subarrays

Consider an array A[1..n] that first increases up to some point p then it decreases until some point q and then increases again. That is A[k] < A[k + 1] for all k in [1..p] and [q..n] and A[k] >...
1 vote
82 views

### Existence of some search algorithms

The lowest time complexity of search algorithms for sorted lists is $$O(n)=logn$$. The lowest time complexity of sorting algorithms is $$O(n) = nlogn$$ So in order to be able to use a search ...
53 views

### Is there any algorithm to find all unique pairs of People with age equal to a given number in less than O(n²)

I have a problem where I have to find all the pairs of a list of People where the sum of their age is equal to a given number under time complexity less than O(N²) ...
112 views

### Simulated Annealing - Intuition

Most versions of simulated annealing I've seen are implemented similar to what is outlined in the wikipedia pseudocode below: ...
1 vote
85 views

### $O(n \log n)$ Algorithm for first Train Problem

On $n$ parallel rails there are $n$ trains with constant speeds $v_1, ..., v_n$. At time $0$ the trains are at positions $k_1, ..., k_n$. Find an $O(n \log n)$ algorithm that determines which trains ...
1 vote
168 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 ...
1 vote
47 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$, ...
119 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 ...
1 vote
92 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, \$\...
1 vote