Galloping Intersection Search
Find intersection of two sorted sequences using exponential jumps followed by binary search.
Tag
Searching
132 notes
Interpolation Search with Fallback
Use interpolation to estimate the target position, with binary search fallback when estimates become unreliable.
SIMD Linear Search
Search several array elements at once using vector instructions.
Cache Aware Binary Search
Arrange and search sorted data with explicit knowledge of cache lines or memory blocks.
Van Emde Boas Layout Search
Search a binary tree stored in recursive cache oblivious layout to reduce memory transfers.
Eytzinger Layout Search
Binary search over an array arranged in heap order to improve cache locality and branch predictability.
Branchless Binary Search
Perform binary search with conditional moves or arithmetic updates instead of unpredictable branches.
Recursive Model Index Search
Use a hierarchy of learned models to predict a key position, then search inside a bounded error range.
Parallel Binary Search with DSU
Answer offline connectivity queries by combining parallel binary search with a disjoint set union.
Parametric Search
Convert an optimization problem into a decision problem and search the parameter space.
12. Specialized Search and Sorted-Order Procedures
Cache-efficient and hardware-tuned search: branchless binary search, Eytzinger and vEB layouts, learned indexes, SIMD search, and galloping intersection.
4. Tree and Indexed Search
Tree-based and indexed search: BST, self-balancing trees, tries, suffix structures, segment and range trees, and spatial trees.
3. Hashing and Table Search
Hash table lookup strategies, open-addressing and chaining variants, probabilistic filters (Bloom, Cuckoo, XOR), and locality-sensitive similarity search.
2. Binary Search and Ordered Search
Binary search and its ordered-search relatives: interpolation, Fibonacci, rotated-array, matrix, parametric, and offline variants.
1. Linear and Sequential Search
Linear and sequential scan techniques including sentinel, bounded, recursive variants, duplicate detection, and majority vote.
01. Searching and Sorting
Searching and sorting techniques spanning sequential and parallel algorithms, from linear scan to GPU-based distribution sort.
Exponential Backoff Search
Expand the search range exponentially until the target is bracketed, then refine within the range.
Merge Path Search
Find diagonal partition points that split a sorted merge into independent balanced ranges.
SIMD Binary Search
Use vector instructions to evaluate multiple candidate positions in a binary search step.
Branchless Lower Bound
Compute lower bound using arithmetic or conditional moves instead of branches.
Learned Index Search
Use a predictive model to estimate where a key should appear, then search within a bounded local range.
Interpolation Sequential Search
Estimate the likely position using interpolation, then refine by local sequential scan.
Finger Search
Search starting from a known nearby position, achieving time proportional to distance rather than full size.
Octree Search
Search for points or regions in 3D space using recursive octant decomposition.
Quadtree Search
Search for points or regions in 2D space using recursive quadrant decomposition.
R Tree Search
Search for spatial objects using hierarchical minimum bounding rectangles.
Cover Tree Search
Nearest neighbor search in metric space using hierarchical covers with exponential scale separation.
VP Tree Search
Nearest neighbor search in metric space using vantage point partitioning.
Ball Tree Search
Search for nearest neighbors in metric space using hierarchical clustering with hyperspheres.
k-d Tree Search
Search for nearest or range points in k-dimensional space using recursive axis splitting.
Range Tree Search
Search for all points within a multidimensional range using layered balanced search trees.
Interval Tree Search
Search for all intervals that overlap a query interval using a balanced interval tree.
LCP Accelerated Suffix Search
Search for a pattern in a suffix array using LCP information to reduce redundant character comparisons.
Suffix Array Binary Search
Search for a pattern in a text by binary searching the lexicographically sorted suffix array.
Suffix Tree Search
Search for a pattern in a text using a suffix tree in time proportional to the pattern length.
Ternary Search Tree Search
Search for a string key in a ternary search tree using character comparisons and three-way branching.
Patricia Trie Search
Search for a key in a Patricia trie using bitwise branching with path compression.
Radix Tree Search
Search for a string or byte key in a radix tree using variable length edge labels.
Compressed Trie Search
Search for a string key in a trie whose unary paths are compressed into edge labels.
Trie Search
Search for a string key in a prefix tree by following character transitions.
Y Fast Trie Search
Search for an integer key using a Y fast trie, combining hashing with balanced trees for linear space.
X Fast Trie Search
Search for an integer key in an X fast trie using hashed prefixes over a binary trie.
Van Emde Boas Search
Search for an integer key in a van Emde Boas tree using recursive universe decomposition.
B Star Tree Search
Search in a B* tree, a B tree variant that keeps nodes denser by redistributing entries before splitting.
B Plus Tree Search
Search in a B+ tree where all records are stored in leaves and internal nodes guide traversal.
B Tree Search
Search for a key in a multiway balanced search tree optimized for block based storage.
Weight Balanced Tree Search
Search in a binary search tree that keeps subtree sizes balanced to guarantee logarithmic height.
Scapegoat Tree Search
Search in a weight balanced binary search tree that rebuilds subtrees to preserve logarithmic height.
Splay Tree Search
Search in a self-adjusting binary search tree that moves accessed nodes toward the root.
Binary Search Tree Search
Search for a key in a binary search tree by exploiting ordering between nodes.
Randomized BST Search
Search in a binary search tree maintained with randomization to achieve expected logarithmic height.
Treap Search
Search in a randomized binary search tree that also maintains heap order over priorities.
Red Black Tree Search
Search in a balanced binary search tree with relaxed balancing using color properties.
AVL Tree Search
Search in a height balanced binary search tree with guaranteed logarithmic depth.
Binary Search
Search a sorted array by repeatedly halving the search interval.
Last Occurrence Search
Find the largest index at which a target value appears in a sequence.
First Occurrence Search
Find the smallest index at which a target value appears in a sequence.
Recursive Linear Search
Linear search expressed recursively by reducing the problem size one element at a time.
Hash Index Probe
Retrieve rows by probing a hash-based index structure using an exact key match.
Hash Join Lookup
Find matching records during a join by probing a hash table built from one relation.
Rabin Karp Search
Search for a pattern in text by comparing rolling hash values before verifying matching windows.
Separate Chaining Search
Resolve hash collisions by storing multiple elements in buckets using linked structures.
Hash Table Lookup
Retrieve a value by computing a hash and probing a table for the corresponding key.
Bounded Linear Search
Linear search restricted to a specified index range within a sequence.
Reverse Linear Search
Scan a sequence from right to left to find the last occurrence of a target value.
Sentinel Linear Search
Linear search optimized by placing a sentinel value to eliminate boundary checks inside the loop.
Linear Search
Scan a sequence from left to right until the target value is found or the sequence ends.
Rolling Hash Search
Search for a pattern in a sequence by maintaining a hash over a sliding window.
MinHash Similarity Search
Estimate set similarity and find similar items using compact MinHash signatures and banding.
SimHash Near Duplicate Search
Find near duplicate documents by comparing compact SimHash fingerprints under Hamming distance.
Locality Sensitive Hashing Search
Search for approximate nearest neighbors by hashing similar items into the same buckets with high probability.
Rendezvous Hashing Lookup
Map a key to the node that receives the highest hash score for that key.
Consistent Hashing Lookup
Map a key to a node by placing both on a hash ring and selecting the next node clockwise.
Binary Fuse Filter Lookup
Test approximate membership using a compact XOR-based filter with improved construction and cache locality.
XOR Filter Lookup
Test approximate membership with a static fingerprint filter built from three hash locations and XOR constraints.
Cuckoo Filter Lookup
Test approximate membership by storing compact fingerprints in cuckoo hash table buckets.
Quotient Filter Lookup
Test approximate membership by splitting a hash fingerprint into quotient and remainder fields.
Counting Bloom Filter Membership
Test membership with a Bloom filter variant that supports deletions using small counters instead of bits.
Bloom Filter Membership
Test set membership with a compact probabilistic bit array that allows false positives but no false negatives.
Minimal Perfect Hashing Lookup
Look up a key using a collision free hash function that maps a static key set to exactly n table positions.
Perfect Hashing Lookup
Look up a key in a static hash table whose hash function has no collisions for the stored key set.
Robin Hood Hashing Lookup
Search in an open addressing hash table that keeps probe distances balanced across keys.
Hopscotch Hashing Lookup
Search in a hash table that maintains elements within a small neighborhood of their home bucket.
Cuckoo Hashing Lookup
Look up a key in a cuckoo hash table by checking a small fixed set of candidate positions.
Double Hashing Search
Resolve hash collisions using a second hash function to define probe steps.
Quadratic Probing Search
Resolve hash collisions by probing with quadratic offsets to reduce clustering.
Linear Probing Search
Resolve hash collisions by scanning sequential slots until the key is found or an empty slot appears.
Last True Binary Search
Find the last position where a monotone predicate remains true.
Equal Range Search
Find the range of indices containing all occurrences of a value in a sorted array.
Upper Bound
Find the first index where elements become strictly greater than a given value.
Integer Square Root by Binary Search
Compute the floor of the square root of a nonnegative integer using binary search.
Monotone Predicate Search
Find the boundary where a Boolean predicate changes value over an ordered domain.
Bisection Method
Find a root of a continuous function by repeatedly halving an interval where the function changes sign.
Offline Binary Search
Answer many monotone queries by processing them together after all input is known.
Parallel Binary Search
Answer many offline queries by searching their answers simultaneously with shared checks.
Powers of Two Search
Search for a boundary by trying decreasing jumps whose lengths are powers of two.
Binary Lifting Search
Find a target state by jumping through powers of two in a precomputed lifting table.
Fractional Cascading Search
Speed up repeated binary searches across related sorted lists by linking sampled elements between lists.
Sorted Matrix Search
Search a matrix sorted by rows and columns using divide and conquer.
Saddleback Search
Search a matrix sorted by rows and columns using a monotone path from a corner.
Matrix Binary Search
Search a row-major sorted matrix by treating it as a virtual sorted array.
Two Dimensional Peak Finding
Find a peak element in a 2D grid using divide and conquer.
One Dimensional Peak Finding
Find an element that is at least as large as its immediate neighbors.
Bitonic Array Search
Search a value in an array that first increases and then decreases.
Rotated Array Minimum Search
Find the smallest element in a sorted array that has been rotated around an unknown pivot.
Rotated Array Search
Search a value in a sorted array that has been rotated around an unknown pivot.
Continuous Ternary Search
Find the maximum or minimum of a unimodal function over a continuous domain.
Discrete Ternary Search
Find the maximum or minimum of a unimodal function defined on discrete indices.
Jump Search
Search a sorted array by jumping in fixed steps, then performing a linear scan within a block.
Fibonacci Search
Search a sorted array using Fibonacci numbers to divide the range.
Uniform Binary Search
Binary search variant that uses precomputed step sizes instead of dynamic midpoint calculation.
Interpolation Search
Search a sorted numeric array by estimating the likely position of the target from its value.
Galloping Search
Expand the search range exponentially from a starting position, then apply binary search.
Exponential Search
Locate a search interval by exponential growth, then apply binary search.
Binary Search on Answer
Find an optimal value by binary searching a monotone feasibility condition.
First True Binary Search
Find the first position where a monotone predicate becomes true.
Lower Bound
Find the first position where a value can be inserted without violating sorted order.
Recursive Binary Search
Binary search implemented using recursion over a shrinking interval.
Iterative Binary Search
Binary search implemented using a loop without recursion.
Unsorted Membership Search
Check whether a value exists in an unsorted sequence.
Local Minimum Linear Search
Find an index where an element is smaller than its neighbors using a linear scan.
Second Maximum Search
Find the second largest element in a sequence.
Second Minimum Search
Find the second smallest element in a sequence.
Boyer Moore Majority Vote
Find a majority element in linear time using cancellation.
Majority Candidate Scan
Find a candidate element that may appear more than half the time using a linear scan.
Frequency Count Search
Count the number of occurrences of a target value in a sequence.
Duplicate Detection by Scan
Detect whether a sequence contains duplicate elements using a direct scan.
Pairwise Min Max Search
Find both minimum and maximum with fewer comparisons by processing elements in pairs.
Min Max Search
Find both the minimum and maximum elements in a sequence using a single pass.
Maximum Search
Find the index of the maximum element in an unsorted sequence.
Minimum Search
Find the index of the minimum element in an unsorted sequence.
All Occurrences Search
Find all indices where a target value appears in a sequence.