Questions tagged [searching]
The searching tag has no summary.
79 questions
0
votes
6
answers
404
views
Efficient data structure for multidimensional lookup
I'm doing a search problem over 18-tuples of non-negative integers. Some tuples are GOOD and some tuples are BAD, and I'm trying to list all of the GOOD tuples exactly once.
It turns out that if a ...
- 873
1
vote
0
answers
121
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 ...
- 11
0
votes
1
answer
197
views
Return indices in the two sum problem
Given an array unsorted P of integers and a number m. I am trying to write a code that returns indices ...
- 138
0
votes
0
answers
48
views
Algorithm to find roots of a "bidimensional function"
The object I am studying is a bit more complicated than a bidimensional function, but I think I can explain what I need better with a simplified example. I can provide more details if asked.
So ...
- 101
1
vote
1
answer
263
views
Algorithm to find approximate position of element from a noisy sorted list
Let's have a static function f(n) which for a given n returns only these answers "lower" or "higher" comparing against an imaginary number x
In a sorted list ...
- 111
0
votes
1
answer
237
views
Databases and B-Trees: What are Keys and how are they related
I confused about the description & definition of "key" occuring as terminology for databases and b-trees.
In first case dealing with theory of databases a key is defined as a choice for ...
- 233
0
votes
2
answers
1k
views
minimum moves for Knight on a infinite chessboard [duplicate]
You are given an infinite chessboard, a knight, a source and a destination.(Normal chess rules apply) we are required to get move knight from source to destination in minimum moves possible.
I can ...
4
votes
1
answer
1k
views
In which situation do we choose randomized binary search instead of the normal binary search?
Both randomized and normal binary search takes O(log n) time complexity but why does the randomized version exist? In other words what is the advantage of randomized binary search even if it has same ...
- 75
1
vote
0
answers
78
views
Efficient data structure for multidimensional searching on intervals and keys
I am searching for a data structure that can capture a database, which is consisted of one column of intervals (like [0, 2], [4, 6]) and one/two columns of keys (...
- 11
1
vote
1
answer
2k
views
Proving correctness of search algorithms
I've seen correctness proofs for other searching algorithms; however, for this particular algorithm: search in a row-wise and column wise sorted matrix, I'm not able to generate a proper proof.
...
user40759
3
votes
5
answers
6k
views
Chess Knight minimum moves to destination on an infinite board
There are tones of solutions for Knights tour or shortest path for Knights movement from source cell to destination cell. most of the solutions are using BFS which seems the best algorithm.
Here is ...
- 268
1
vote
2
answers
418
views
Array contains elements that differ by K correctness proof
I have been puzzling over an algorithm that decides whether a sorted array of numbers contains two numbers that differ by k. I do not intuitively understand why ...
- 121
3
votes
1
answer
2k
views
Average-case complexity of linear search where half of the elements in the array are duplicates
I know that for an array of size n distinct elements, the Average Case complexity for linear search is as follows:
A(n) = $\frac{n + 1}{2}$
However, I am having trouble coming up with the Average ...
- 33
1
vote
1
answer
2k
views
Understanding Binary Search for Kth Smallest element in an Array
The Answer here shows a way to solve the problem with O(1) space. The approach uses Binary Search. I am finding really hard to wrap my head around why it works. I get why we did low + (high-low)/2 ...
- 119
0
votes
1
answer
1k
views
Consistent heuristic and A*
The following graph has consistent heuristic.
An A* algorithm will alter its first guess ACD to the correct shortest path ABD... if it has consistent heuristic, doesnt it mean, that AB should be found ...
- 1