Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

Questions tagged [search]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
12 votes
3 answers
2k views

Why are search problems assumed to have the structure of "find a path in a graph"?

I have skimmed a few introductions to "search problems", and I have noticed that: Stated informally search problems are defined as "find an object y inside a larger space/object X"...
user56834's user avatar
  • 3,882
0 votes
0 answers
22 views

Search a list of conditions

If I have a list of conditions: and(a,or(b,c)) not(b) or(a,c) and(a,d) or(or(or(a,b),c),d) and I'm given values for these conditions, let's say, ...
Gatonito's user avatar
  • 111
0 votes
1 answer
177 views

How do I prove correctness of my algorithm that finds a pair of integers in an array that have a sum of 0?

I have designed an algorithm (up to making a pseudocode) that accepts a sorted array as input and finds in $O(n)$ time if there's a pair of elements (integers) in the array that have a sum zero. What ...
Tita's user avatar
  • 225
0 votes
1 answer
45 views

maximum length of the sequence (a[i],b[i]) such that if $b[i]='<'$ then $a[i+1]<a[i]$ and if $b[i]='>'$ then $a[i+1]>a[i]$

Let $N$ be a number and consider the sequence of $a[i]$, $b[i]$ with $i=1,n$ where $a[i]$ are positive integers and $b[i]$ is the sign '$<$' or '$>$'. Find the maximum length of the subsequence(...
shangq_tou's user avatar
0 votes
0 answers
100 views

Find a range of values to subset the rows to maximize the objective function

I have searched around for some time but couldn't find a similar example to my problem. It looks common enough that I would expect it to be solved. It lies between search and optimization/regression. ...
user19346's user avatar
0 votes
2 answers
153 views

Efficient search in a permutation

Let $S$ be an array of length $n$ containing a random permutation of numbers from $0$ to $n-1$. What is the most efficient (in expectation) algorithm for finding the location of a given number $k$ in $...
Dmitry Kamenetsky's user avatar
2 votes
1 answer
829 views

Difference between cost and the heuristic function in A* search

Looking at the image above, thinking in terms of A* search. I don't fully understand the heuristic function. The cost makes sense, so thinking in terms of a traditional map or navigation scenario. I'd ...
Ewan Valentine's user avatar
0 votes
0 answers
175 views

Frontier steps for greedy best first search

I've been asked to list the frontier steps for greedy best-first search for the graph in the picture below. I've attempted to recreate the algorithm in Golang, as shown below: ...
Ewan Valentine's user avatar
1 vote
0 answers
75 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', ...
Surprised Seagull's user avatar
2 votes
1 answer
150 views

Efficient "radius-search-based averaging" algorithm on a set of 3-D points that lends itself to massive parallelization without locking

I'm looking for a good algorithm for "simple radius-search-based averaging" (or "radius search based sub-sampling") as referred to section 3.4 of the DynamicFusion article. ...
Greg Kramida's user avatar
-1 votes
1 answer
608 views

How to find time complexity of Breadth First Search for this tree?

This is what I got from another forum, but honestly doesn't make much sense to me. Time complexity for a single tree doesn't make a lot of sense, since the function in the big O notation might be ...
abdellah neven's user avatar
2 votes
1 answer
86 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: ...
Daniel Donnelly's user avatar
2 votes
2 answers
818 views

Searching through an unsorted array with a better than O(n) complexity?

This question kind of puzzled me, it was presented as a homework assignment for 2nd year undergrads and one of them approached me in case I could give him some pointers, but the problem is I couldn't ...
user avatar
0 votes
1 answer
284 views

Why is a regex search less efficient than a normal search?

On a lot of messaging applications, regex search isn't enabled due to a "linear scan". I'm not sure why this is the case. Can someone explain?
Neel Sandell's user avatar
2 votes
1 answer
237 views

How to find long trails in a multidigraph

I have a directed multigraph (a multigraph is a graph that can have more than one edge between any two nodes). In Wikipedia's terminology, this is a directed multigraph (edges without own identity). I ...
user2373145's user avatar
1 vote
0 answers
45 views

Given consumer grade hardware,what is a reasonable upper bound for size of search space?

There's a gacha RPG I'm trying to get better at. I estimate there are about 10^15 states for the 3 opening rounds of a match for which I am trying to evaluate damage output. The equations themselves ...
Hyouin Kyouma's user avatar
0 votes
1 answer
32 views

Question regarding the assumptions of the No-Free-Lunch-Theorem for Search

I am trying to understand the No-Free-Lunch-Theorem for search (can be found here: http://axon.cs.byu.edu/~martinez/classes/678/Papers/Wolpert_NFLsearch.pdf) and have a question regarding the ...
asdfsolider's user avatar
0 votes
0 answers
10 views

Finding the point with smallest x-ordinate between two given y-ordinates [duplicate]

Given a set of points P=p1,p2,..pn in R2 in where pi=(xi,yi),finding the point with smallest x-ordinate having y-ordinates between y1 and y2, where y1 and y2 are given as inputs. I can compare the ...
Arkaprava Paul's user avatar
0 votes
2 answers
256 views

$O(\log n)$ search algorithm for a sorted natural number array with block of 0s on right

Assume A is an m sized array containing n ($m \ge n$) natural numbers (excluding $0$), sorted on the left of it. All remaining cells on right are filled with zeros. For example, $m=10, n=4$: $$A = \{...
David's user avatar
  • 1
1 vote
1 answer
261 views

Can all types of computational problems be modeled as decision problems?

Can all types of computational problems (search, counting, optimization...) be modeled as (sets of) decision problems? Rephrased: For every type of computational problem is there a set of decision ...
DeeDee's user avatar
  • 345
0 votes
2 answers
696 views

The best approach to search for closest object in hash map holding arraylist without changing data structure

Imagine the game handled server sided, don't think of a visual problem. Given a game 2D map, with size of n * n. The game contains objects (such as door, wall, a table). Each tile position (x,y) can ...
Ben's user avatar
  • 1
0 votes
3 answers
195 views

Need help with adding elements to hashtable with linear probing

Here is an example problem which I have having trouble figuring out. The red text is the answer. I get how the values are added before the hashtable is resized... that is common sense. (Insert 0 at ...
Software Developer's user avatar
0 votes
1 answer
53 views

Pagination of results from different sources merged by a unified scoring function

Assume a Hotel reservation scenario, given $m$ ranked lists of attribute values such as distance, price, amenities (normalized between $0$ and $1$), and a unifying linear score function $F(\cdot)=\...
mhn_namak's user avatar
  • 227
-3 votes
1 answer
43 views

Is Google search personalized? [closed]

Pardon me if this is a very naive question. Suppose I search for something on Google and my next-door neighbour searches for the same thing (on Google) at the same time. Do we get the same or ...
Siddhartha's user avatar
3 votes
3 answers
426 views

Does White never lose in Chess if Chess is solved?

If the machine has enough memory and speed as to compute all states of the Chess game in a reasonable time, can a player with the white pieces - operated by a machine - lose a game?
108880's user avatar
  • 27
1 vote
0 answers
17 views

Is there a high-level framework from which all known search and optimization algorithms can be derived?

The fields of applied math and computer science are inundated with optimization algorithms, variations on those optimization algorithms, and variations on those variations. I'm mainly talking about ...
StrongOptimizer's user avatar
0 votes
2 answers
2k views

Fastest algorithm to find whether a list contains a word?

Given an unordered list of words, what's quickest way to test whether a certain word is in that list? I can't think of another way to do this other than just going through each element in the list ...
fallingriptide's user avatar
2 votes
1 answer
96 views

Extend binary search

There is a way for finding K entries of N given entries using a binary search? I mean, I have N entries, indexed from 0 to $N-1$ and I have to find $K$ of them that satisfy some constraint. The ...
NM2's user avatar
  • 121
2 votes
1 answer
1k views

Search vs planning in artificial intelligence

I'm studying artificial intelligence following the Russell & Norvig book. We did a search and planning part that for me is the same (at least on the representation). I'd like to know what is the ...
theantomc's user avatar
  • 262
3 votes
1 answer
81 views

Finding $k$-th element in prefix of size $i$

Let's say we are given array $A$ of size $n$. We need to answer some numbers of queries. For each query we are given index $i$ and integer value $k$, $k \le i$. If we take the first $i$ elements of ...
someone12321's user avatar
  • 1,428
1 vote
1 answer
107 views

Kth smallest element in an arra [duplicate]

What would be an efficient method to find the kth smallest element in an array with worst case time complexity being $ O(n) $?
SiluPanda's user avatar
  • 549
1 vote
1 answer
4k views

What is a search problem?

I'm looking for a formal and broad definition. Intuitively, I would say that a problem where various checks have to be done is a search problem. Is this the only criteria? How can we know that a ...
Lay González's user avatar
1 vote
0 answers
63 views

An algorithm for getting the position index

Consider these two equation. $$ m_1+m_2+m_3+m_4 = M_m\\ |m_1|+|m_2|+|m_3|+|m_4| = N_m $$ where $\{m_i,M_m,N_m\}\in \mathbb{Z}$. Given the value of $(N_m,M_m)$ we can find the different solutions ...
Hubble07's user avatar
  • 111
4 votes
1 answer
987 views

Heuristics vs meta-heuristics vs hyper-heuristics?

The wikipedia page on meta-heuristics states that they are "heuristics designed to find, generate, or select a heuristic". The wikipedia page on hyper-heuristics states that they are "heuristic ...
user626625's user avatar
2 votes
1 answer
3k views

A* Search Algorithm Implementation with Priority Queue

I've got a question regarding the A* search algorithm's implementation. According to Wikipedia, one has to use a priority queue for retrieving the next node with the lowest f value, is it possible to ...
Rafi's user avatar
  • 23
2 votes
0 answers
51 views

B/B+ trees without leftmost pointers

In both B-trees and B+trees, a node (a.k.a page) contains K keys and K+1 pointers: node = [ ptr_1, key_1, ... , ptr_K , key_K , ptr_(K+1) ] Now suppose that I ...
Ali's user avatar
  • 121
0 votes
1 answer
238 views

Steps to create a heuristic for solving a problem

I am completely new to AI and doing self-learning to acquire this knowledge. I went through the different available search algorithm like BFS, DFS and A* but something that I can't understand is a ...
RAZ's user avatar
  • 3
2 votes
1 answer
77 views

How does topic or tag suggestion algorithms work?

I know it's a keyword based search. But sites like Quora have some good suggesting algorithms where the algorithm understands the intent of question asked rather than just the keywords meanings. For ...
Himanshu Kansal's user avatar
1 vote
1 answer
37 views

Better algorithm for aggregating data from various LDAP systems

I have 10 LDAP systems which contain users and groups in the form of objects. Each user / group is identified by a distinguishedName like ...
SimpleGuy's user avatar
  • 215
1 vote
1 answer
317 views

Black-box combinatorial optimization problem over permutations

I am solving general black-box optimization problems like: x*: f(x) -> min, where x are permutations of length N (N = 50 for example, so brute force search is not possible). Objective function f(x) is ...
michal's user avatar
  • 103
1 vote
1 answer
45 views

Is graph search of shortest (optimal) path an instance of optimisation?

I am familiar with mathematical (gradient-based) optimisation methods, some heuristic methods like GAs or linear programming methods like simplex algorithm. I am not too familiar with graphs / trees ...
A.L. Verminburger's user avatar
2 votes
2 answers
134 views

Non-quadratic search for specific difference between elements in sorted array

New to computer science and am attempting to verify if there are any non-quadratic approaches (i.e. better performance than Big-O of n^2) for finding a potential specific difference between either ...
AdjunctProfessorFalcon's user avatar
6 votes
1 answer
323 views

Is there a polynomial time algorithm to determine whether an 'up down' language is 'emptible'?

Definitions: An up down language is a language whose alphabet is a set of pairs, but not characters, of two characters, where the one character in the pair is the opposite of the other character in ...
Farewell Stack Exchange's user avatar
1 vote
1 answer
2k views

special case of best first search algorithms

I read somewhere that DFS is a special case of Best first search algorithm if f(n)=-depth(n). please justify this i am not getting it.:/
mehru's user avatar
  • 11
7 votes
1 answer
428 views

What is the most recent comparison of signature files and inverted indices?

Modern papers on search indices often contain a statement that inverted indexes (posting lists) are categorically superior to signature files (bloom filters). Here are some examples from papers ...
dan's user avatar
  • 529
0 votes
0 answers
105 views

Algorithmic complexity of Sub-array with sum = target algorithm

Question: Given an array of positive integers and a target total of X, find if there exists a contiguous subarray with sum = X E.g: If array is [1, 3, 5, 18] and X = 8 Output: True, if X = 10, ...
Smart Home's user avatar
0 votes
1 answer
719 views

Ski design usaco problem alternative solution

problem statement for SKICOURSE is this Farmer John has N hills on his farm (1 <= N <= 1,000), each with an integer elevation in the range 0 .. 100. In the winter, since there is abundant snow ...
manifold's user avatar
  • 111
1 vote
1 answer
120 views

Taking intersection in large search

As I understand, you can build the the word -> pages index in Google or large SQL database since indexed search has complexity O(1) -- lookup gives you a billion-page result at once ...
Little Alien's user avatar
6 votes
2 answers
3k views

Understanding Levin's Universal Search

I am having troubles understanding Levin's universal search method. In Scholarpedia, http://www.scholarpedia.org/article/Universal_search, it is claimed that “If there exists a program $p$, of length $...
Don Arturo's user avatar
10 votes
1 answer
963 views

Why Is KD-Tree-based Nearest Neighbor Exponential in K?

I've read in many papers on higher-dimensional nearest neighbor search that KD-Trees are exponential in K, but I can't seem to determine why. What I'm looking for is a solid runtime-complexity ...
akdom's user avatar
  • 200