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
votes
0answers
47 views

Logarithmic Time — O(log n) in Python

Hi , I am new to Data Structure and trying to get some clarifications. Following shows an example Logarithmic Time — O(log n) in Python. ...
1
vote
1answer
17 views

Efficient calculation or estimation of “minimized combined Manhattan distance” between two sets of points

I’m attempting to write a heuristic for an implementation of A* search. The problem involves rearranging cells in a 3D grid until they match a particular solved state. I’m looking for options for a ...
0
votes
0answers
11 views

Are arc inconsistencies predictable?

Are arc consistency algorithms such as AC-3 inevitable for CSP to be solved more efficiently through pruning of inconsistent values? Can't we use the constraints that we have and predict arc ...
0
votes
0answers
43 views

Finding first occurence of all possible matches?

Say you have multiple strings that you're trying to match in a text. And it's possible all these strings have a match in the text. Is there a good way to return out of all the matching strings the ...
0
votes
0answers
46 views

Algorithm for sorting arrays of arrays

I have a problem where I need to sort array of arrays. For A being a array arrays (a1,a2,a3,...an) were each a = {0...d} d=fixed number of elements. *The assumption all sublists will have fixed ...
0
votes
0answers
20 views

Extending a solution in backtracking

Steven Skiena's "Algorithm Design Manual" has the following code for the backtracking algorithm: ...
1
vote
1answer
81 views

Minimum number of given operations in order to group letters in a string

Description Suppose we have a string containing letters 'A', 'B', 'C', 'D', and the characters are placed in a stack. We also have an empty stack. Ultimately, we want all of the same letters to be ...
2
votes
1answer
42 views

Error in pivot selection algorithm for merge phase [Sorting]

In the paper Comparison Based Sorting for Systems with Multiple GPUs, the authors describe the selection of a pivot element with respect to the partition on the first GPU (and its mirrored counterpart ...
0
votes
1answer
28 views

Fast hashing algorithm for mapping/quantizing a collection of floats onto a small set of sorted floats

With my application, I have Collection X: thousands of floating-point numbers with the value range [0, 1], not sorted. Collection Y: 11 floats ranging from [0, 1], sorted. The size of X is known. Let ...
5
votes
1answer
32 views

Isn't this Commentz-Walter algorithm buggy?

I've been trying to piece together an implementation of the Commentz-Walter string search algorithm. The idea is to construct a state machine from a trie, working backwards from the earliest feasible ...
0
votes
0answers
40 views

Which advanced data structure to use?

For range queries on a subarray [L,R] , I want to find all the indices of successive maximums from left to right within O(log(R-L+1)), excluding index "L". I know using segment trees I can ...
6
votes
1answer
142 views

Binary-ish search through partially ordered set

I have an interesting function. It takes subsets of {1,...,N} to positive integers, i.e. $f:P([N]) \rightarrow Z^+$. I know that if S is a subset of S', $f(S) < f(S')$. Also, if S and S' have the ...
2
votes
1answer
36 views

How do you find all integers in a sorted array of size n that appear n/k times?

I try to find the solution to this problem: How do you find all integers in a sorted array of size n that appear n/k times in less than O(klogn) time? I could only find this question, where O(klogn) ...
1
vote
0answers
53 views

Searching a 2D array of binary Data

I'm working on optimizing the structure of an optical meta device. I have a randomly generated 2D matrix, where 0,1 represents the presence/absence of a hole. Each structure manipulates light ...
0
votes
3answers
27 views

What algorithm should I use to find the closest solution to a given total using a list of integers?

My problem is this: Let's say I have an arbitrary list of integers A[2013, 54, 3, 32 1, 23...] What is the best strategy to find which of those numbers I should add together to have a sum equal or ...
1
vote
0answers
11 views

Batching multiple nearest surface queries: Is it faster? Are there better algorithms?

I'm working on an algorithm that computes lots of "nearest point on a triangulated surface" queries in 3d as a way to resample data sets, and I'm wondering if there is any information out ...
1
vote
0answers
30 views

Set data structure for data too large to fit into memory

I'm trying to solve the following exercise: Given N data items and memory that can hold M/B blocks of size B. Describe a data structure that needs at most N/B blocks of external memory and allows ...
1
vote
2answers
52 views

Theoretical lower bound of finding number of occurrences of a target integer in a sorted array

Given a sorted array of integers and a target integer, find the number of occurrences of the target integer. It is well-known that a binary search has time complexity $O(\lg n) $ where $n$ is the ...
2
votes
2answers
55 views

Efficient Data Structure for Closest Euclidean Distance

The question is inspired by the following UVa problem: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&category=18&page=show_problem&problem=1628. A network of ...
2
votes
1answer
41 views

O(m+n) Algorithm for Linear Interpolation

Problem Given data consisting of $n$ coordinates $\left((x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\right)$ sorted by their $x$-values, and $m$ sorted query points $(q_1, q_2, \ldots, q_m)$, find the ...
1
vote
1answer
21 views

Search a number

Given n numbers, design an algorithm to find the smallest $n^{\frac{2}{3}}$numbers, in sorted order. (Assume $n^{\frac{2}{3}}$ is an integer.) I don't understand this question. Can I simply $x = n^{\...
1
vote
2answers
52 views

Algorithm for optimal rule-based arrangements?

I am trying to plant a row in a garden. Certain plants are good for some plants and bad for others, and I am trying to find the best order of plants: most adjacent friends and no adjacent foes, as ...
0
votes
1answer
30 views

Find Best N Points From a Graph

I've given a task and wonder if there are any better solutions. Inputs of task are: Distance of district pairs Population of pairs Goal is: Find n districts at which its population and districts ...
0
votes
0answers
12 views

Parsing text, then searching it: one entry per position, vs. 1 JSON column per text

I have a Rails application using Postgresql. Texts get added to the application (ranging in size -- as short as a few words, to as long as, say, 5,000 words?). The text gets parsed, both ...
0
votes
0answers
21 views

Powells Method for 2 Variables?

I've been studying this YouTube video on Powells method and it looks like when we have a single variable we start at the upper and lower bounds of the variable and then we keep dividing the search ...
0
votes
0answers
23 views

What datastructure does google use to store its search engine indexes?

To the best of my knowledge search engines such as Google index the web using MapReduce amongst many other tools. With my limited experience this would make hash tables the most practical option for ...
1
vote
1answer
30 views

What solution to apply for finding the optimal parameters?

For a study, I have a system (black-box) that requires an input in the form of an array with 4 values (input_array) and depending on their values it produces an ...
0
votes
1answer
21 views

N 3d integer points in box with maximum average distance

given a 3d cube with a size of m x m x m, is there an efficient algorithm to find N integer points with the average Euclidean distance between each pair maximized? If not, is there any evolutionary ...
0
votes
1answer
17 views

Search Space for Population Metaheuristic Optimization Problem

Given that x objects (repetition allowed) can be arranged into y configurations, and that the population size is N, I am uncertain as to whether the size of the search space is |S| = |(y^x) * N| or |S|...
3
votes
1answer
57 views

Are there graphs for which A* cannot be admissible?

Wikipedia states that "On infinite graphs with a finite branching factor and edge costs that are bounded away from zero $ (d(x,y)>\varepsilon >0$ for some fixed $\varepsilon$), A* is guaranteed ...
1
vote
0answers
18 views

Rabin Karp algorithm that uses bitwise AND

I'm reading the source code of JPlag and came across their rabin-karp algorithm implemented found here. Here's the gist of it: ...
2
votes
1answer
32 views

Definition and example of search problem

I searched the pages a lot about the search problem but didn't understand much, so please make it clearer for me. WIKIPEDIA: In computational complexity theory and computability theory, a search ...
1
vote
1answer
32 views

Algorithms (optimization problem): find collection of objects whose permutation satisfies criteria

I'm putting together a personal list of recipes that I enjoy, and would like to construct an algorithm that parses this recipe database and automatically builds me a meal plan for the week. For N ...
0
votes
3answers
47 views

Finding the point with minimum x-ordinate, lying between two y-ordinates

Given a set of points $P=p_1,p_2,..p_n$ in $R^2$ in where $p_i=(x_i,y_i)$,finding the point with smallest x-ordinate having y-ordinates between $y_1$ and $y_2$, where $y_1$ and $y_2$ are given as ...
0
votes
1answer
123 views

Average number of inspections

Consider a set of n elements whose key values are $$0, 1, ..., n−1.$$ Let $p(i) (0 ≤ i ≤ n−1) $ be the probability that the element with key i is searched. Assume the following distribution of $p(i)’s$...
0
votes
0answers
33 views

2 Partition Problem

I want to solve the two partition problem (https://en.wikipedia.org/wiki/Partition_problem) using an uninformed search algorithm (BFS or uniform cost). The states can be represented by three sets S1,...
1
vote
1answer
30 views

Proving 2 heuristics are admissible

We have $h_1(n)$ and $h_2(n)$ which are both admissible heuristics. We know that $h_1(n) < h_2(n)$ for every state $n$ in a search problem. Now we are given two heuristics $h_3(n)=\frac{h_1(n)}{1+...
1
vote
1answer
42 views

Are there search algorithms that perform better on a Rope than a String?

I want to implement fast text-search over a Rope data structure. That is, a B-Tree of characters, where the characters are not sorted. (Meaning the standard way to search in a B-Tree by key does not ...
0
votes
0answers
83 views

Time Complexity of Tabu Search Algorithm

I am trying to find the time complexity of Tabu Search. But I could not find any resources. Any need is appreciated.
1
vote
1answer
92 views

Understanding Randomized Select algorithm

Here is the algorithm in pseudo code: Where $A$ is the array to search, $p$ is the starting index in the array, $r$ is the ending index and $i$ represent the number of smaller values we want from ...
0
votes
1answer
31 views

Shortest path form node X to nodes A, B, C in graph

I have an unweighted consistent graph and some node X(the source) and some nodes A, B, C and more. I need to find the shortest paths: X->A, X->B, X->C and ...
1
vote
2answers
16 views

How to store set of long char strings to search for long char string key

I have a set of several thousand strings of max length 1024 (containing all visible ASCII chars plus space) I need to store to make it fast to search for an exact match of a key. What is the best ...
1
vote
1answer
64 views

Amount of expected loop iterations when searching an array by random index

Lets say we have an array A of size n. It has 1 as its first index and n as its last index. It contains a value x, with x occurring k times in A where 1<=k<=n If we have a search algorithm like ...
0
votes
0answers
27 views

Transits directions search

Data Description : A database consisting of many Transits. Each transit has its own Path (both forward and backward), and each path has a set of Stops. Each stop consists of the position and the ...
1
vote
0answers
77 views

Should a prefix tree (trie) node store only a single character or a string?

I've just implemented a Trie and I thought it would be a good idea to store strings in the Trie nodes in contrast to storing single characters. Storing strings is for sure more space-efficient and ...
2
votes
1answer
29 views

Finding maximally far away points

Given a metric space $X$ with finitely many points, and a nonnegative integer $n$, I want to find a set of $n$ points in $X$ which maximizes the minimum distance between any two points. What ...
1
vote
1answer
34 views

Data structure for equivalence classes

Let $E$ be an equivalence relation defined over a set $S$. The access to $E$ is only via queries of the form $M(s_1,s_2) = 1$ if $s_1$ and $s_2$ are in the same class and $0$ otherwise. Computing $M$ ...
0
votes
1answer
30 views

For what data structures is jump search practically useful?

Jump search is a search algorithm for sorted lists which runs in $O(\sqrt n)$ time, but has the advantage of only making backwards steps at the end (and given the ability to make arbitrarily long ...
0
votes
1answer
50 views

Sqrt(x) function implementation; what is $(i^2 \leq x) \land ((i + 1)^2 > x)$ checking?

Recently I was working on a LeetCode question ...
2
votes
0answers
25 views

What's a minimum-window alpha beta search algorithm?

I was skimming the Deep Blue overview paper and on page 242 it says: "The search control does not really implement the regular αβ search algorithm. Rather it implements a minimum-window αβ search ...

1
2 3 4 5
12