# Questions tagged [search-algorithms]

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

698 questions
Filter by
Sorted by
Tagged with
3k 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"...
• 4,002
16 views

### What algorithm should be used to find the closest set of dates?

I have tried to outline my problem as structured as possible, here is a rough overview, I am trying to find the best matching stay for a hotel booking system. If someone inputs check in and checkout ...
1 vote
134 views

• 159
10 views

### The Multi-Room Muddy Forehead Puzzle with Varied Color Perception

Imagine there are n children, and they are divided into three separate rooms (Room A, Room B, Room C) without knowing how many children are in each room. As before, their foreheads are marked with ...
• 139
223 views

### Minimum number of comparisons to find $2$nd smallest element

Show that the second smallest of $n$ elements can be found with $n+\lceil\lg n\rceil-2$ comparisons in the worst case. (Hint: Also find the smallest element.) [1] I tried but I have no idea how to, e....
• 159
56 views

### Graph Search Algorithms that are practically fast on dense graphs

I'm trying to do some research on graph search algorithms that are practically fast on relatively dense graphs. Besides the common ones like A* or Dijkstra's, what are some graph search algorithms ...
1 vote
37 views

### Algorithms/Data-Structures to calculate transitive call graphs in the presence of virtual dispatch?

Algorithms/Data-Structures to calculate transitive call graphs in the presence of virtual dispatch? I am trying to write a program to analyze Java programs and figure out the transitive closure of the ...
• 85
38 views

### Data structure for arithmetic logical queries

Abstract Problem I'm looking for a data structure that will (1) allow me to make queries of the form A.x - B.x <= 0.1 AND A.y + B.y >= C.y + D.y and (2) allow ...
• 161
105 views

### How to cover elements with minimum amount of elements

I'm trying to create a game but I am having some difficulties in coming up with a suitable algorithm for my problem. I have elements from 1 to n and I am trying to cover all of the elements using the ...
1 vote
88 views

### Difference between Hadlock's algorithm and A* search

I recently read about pathfinding algorithms on grids. It seems two of the most popular are Lee's algorithm and Hadlock's algorithm. Other than the space optimizations that these algorithms employ, it ...
• 225
82 views

### Finding an approximate double-zero using binary search

Let $f$ be a continuous real function on $[-1,1]$. The function is accessible via queries: for any $x$, the value of $f(x)$ can be computed in constant time. If $f(-1)<0$ and $f(1)>0$, then by ...
• 6,122
1 vote
142 views

### Simplified Memory Bounded A*

I have been studying the SMA* algorithm and I am having trouble understanding the backup operation. Specifically, I don't understand why the f value of a child node should be the maximum of its own f ...
42 views

• 191
341 views

### Understanding Rabin-Karp's rolling hash computation

Possibly related to this. Let $T$ be the text and $n$ be the length of the pattern. I understand that if substrings of $T$ are interpreted as base-$d$ numbers where $d$ is the alphabet's size, then ...
• 183
193 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 ...
• 225