tag

#ordered-data

28 pages tagged

Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.18 Skip Lists

7.18 Skip Lists Balanced trees provide logarithmic performance through carefully maintained structure. AVL trees track heights. Red-black trees track colors. B-trees manage node occupancy. All of these structures require specialized balancing logic. Skip lists achieve similar performance with a radically different idea. Instead of maintaining a balanced tree, a skip list maintains multiple linked lists layered on top of one another. Higher levels contain progressively fewer elements, allowing searches to...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.3 Upper Bound Searches

7.3 Upper Bound Searches Lower bound finds the first position whose value is greater than or equal to a target. Upper bound solves the complementary problem: it finds the first position whose value is strictly greater than the target. At first glance, the distinction appears minor. In practice, upper bound is one of the most useful operations in ordered data structures because it identifies the position immediately after a group...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.10 Ordered Maps

7.10 Ordered Maps Arrays are excellent when data rarely changes. Binary search provides fast lookups, but insertion and deletion are expensive because elements must be shifted to preserve ordering. Many real systems require both efficient searches and efficient updates. Databases insert records continuously. Schedulers add and remove tasks. Caches expire entries. Financial systems process streams of orders. In these environments, rebuilding or resorting an array after every modification is impractical....
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.22 Sparse Tables

7.22 Sparse Tables Many range-query structures support updates. Segment trees allow values to change. Fenwick trees support dynamic sums. Balanced trees continuously adjust their structure. Sometimes updates never occur. The data is loaded once, queried thousands or millions of times, and never modified. Examples include: Historical datasets Compiled lookup tables Immutable logs Static geographic data Read-only analytics snapshots Competitive programming query sets When updates disappear from the problem, we can...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.15 Red-Black Trees

7.15 Red-Black Trees Red-black trees are self-balancing binary search trees with a relatively loose balance condition. They do not try to keep the tree as strictly balanced as AVL trees. Instead, they enforce a small set of color rules that guarantee the tree height remains logarithmic. This trade-off makes red-black trees practical. They provide predictable performance, handle frequent updates efficiently, and avoid excessive rotations. For that reason, they are widely...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.16 AVL Trees

7.16 AVL Trees AVL trees were the first self-balancing binary search trees. Introduced in 1962 by entity["people","Georgy Adelson-Velsky","AVL tree co-inventor"] and entity["people","Evgenii Landis","AVL tree co-inventor"], they established many of the balancing techniques that later tree structures would adopt. The defining characteristic of an AVL tree is strict balance. Every node tracks the relative heights of its left and right subtrees. Whenever an insertion or deletion causes that difference to become...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.21 Fenwick Trees

7.21 Fenwick Trees A Fenwick tree, also called a binary indexed tree, is a compact data structure for prefix sums and point updates. It solves a narrower problem than a segment tree, but it solves that problem with less code, less memory, and excellent constant factors. If your operation is sum-like and your updates affect one position at a time, a Fenwick tree is often the cleanest choice. The structure...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.6 Floating-Point Binary Search

7.6 Floating-Point Binary Search The examples in previous sections searched integer domains. Many real-world problems involve continuous values where the answer is not an integer and may not even have an exact representation in memory. Examples include geometric measurements, physical simulations, financial calculations, optimization problems, and numerical analysis. In these domains, the goal is often to approximate a value within an acceptable error tolerance rather than compute an exact answer....
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.17 B-Trees

7.17 B-Trees Binary search trees work well in memory, where following a pointer from one node to another is relatively cheap. Storage systems have a different cost model. Reading one value at a time from disk or flash is expensive compared with reading a block of adjacent values. B-trees solve this problem by making each node hold many keys and many children. Instead of branching two ways at each node,...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.12 Binary Search Trees

7.12 Binary Search Trees Before studying specific balancing algorithms such as AVL trees and red-black trees, it is worth understanding the structure they are trying to preserve. The binary search tree (BST) is one of the most influential data structures in computer science. Many advanced structures are refinements of the BST idea rather than completely new inventions. AVL trees, red-black trees, treaps, splay trees, B-trees, and database indexes all build...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.11 Balanced Trees

7.11 Balanced Trees A binary search tree provides an elegant framework for maintaining ordered data. Search, insertion, deletion, predecessor queries, successor queries, and range scans all follow naturally from the ordering relationship between nodes. There is one problem. Nothing prevents a binary search tree from becoming badly shaped. Consider inserting values in sorted order: 1 2 3 4 5 6 7 A naïve binary search tree becomes: 1 \\n 2...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.24 Search Structures in Databases

7.24 Search Structures in Databases Most discussions of search algorithms focus on in-memory collections. Arrays, trees, heaps, and hash tables are useful abstractions, but real-world data often resides on storage devices, across networks, or in distributed systems. Database search structures are designed around a different set of constraints: Disk and SSD access latency Cache efficiency Concurrency Durability Range scans Large datasets As a result, database indexes often look different from...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.23 Order Statistics Trees

7.23 Order Statistics Trees Many search problems ask for more than membership. Instead of: Does key 42 exist? the question becomes: What is the 42nd smallest value? How many values are smaller than X? What is the rank of this item? What is the median right now? Standard balanced trees support efficient search, insertion, and deletion, but they do not directly answer these order-based questions. Order statistics trees extend balanced...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.1 Binary Search Template

7.1 Binary Search Template Binary search is a boundary-finding algorithm. The common beginner description says that binary search finds an item in a sorted array, but that description is too narrow. The more useful version says this: Given an ordered search space and a monotone predicate, binary search finds the first position where the predicate becomes true, or the last position where it remains false. That framing covers exact lookup,...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.25 Parametric Search

7.25 Parametric Search Parametric search is a technique for solving optimization problems by repeatedly answering decision questions. It is closely related to binary search on answer. The distinction is mostly one of emphasis. Binary search on answer describes the implementation pattern. Parametric search describes the modeling step: turn an optimization problem over a parameter into a sequence of feasibility tests. Instead of directly computing the best value, you ask whether...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.14 Treaps

7.14 Treaps Most balanced tree structures maintain balance through carefully designed invariants. AVL trees track subtree heights. Red-black trees maintain color constraints. B-trees enforce node capacity rules. Treaps take a different approach. Instead of explicitly maintaining balance, they introduce randomness. A treap combines two structures: A binary search tree on keys A heap on priorities The name comes from this combination: Tree + Heap = Treap The result is a...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.4 Search on Answer

7.4 Search on Answer Most binary search examples begin with a sorted array. In practice, some of the most powerful applications of binary search involve no array at all. Instead of searching for a value inside a collection, you search for the answer itself. This technique, commonly called binary search on answer , transforms optimization problems into decision problems. Rather than asking: What is the optimal value? you ask: Is...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.20 Segment Trees

7.20 Segment Trees Segment trees are among the most versatile range-query data structures in algorithm design. A prefix-sum array answers static range-sum queries efficiently, but updates are expensive. A Fenwick tree supports dynamic sums, but its capabilities are somewhat specialized. Segment trees generalize the idea by storing information about intervals rather than individual values. This seemingly simple idea allows a segment tree to answer a wide variety of range queries:...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.7 Rotated Arrays

7.7 Rotated Arrays Standard binary search assumes the entire array is sorted. Rotated arrays violate that assumption while preserving enough structure to remain searchable in logarithmic time. A rotated array begins as a sorted sequence and is then shifted around a pivot point. For example: Original: [1, 2, 3, 4, 5, 6, 7] Rotated: [5, 6, 7, 1, 2, 3, 4] Although the array is no longer globally sorted, each...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.8 Peak Finding

7.8 Peak Finding Binary search is often associated with sorted data, but some of its most elegant applications work on arrays that are not sorted at all. Peak finding is one such example. A peak is an element that is greater than or equal to its neighbors. The array may rise and fall multiple times, contain local maxima, and have no global ordering. Despite this apparent lack of structure, a...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.2 Lower Bound Searches

7.2 Lower Bound Searches The most useful form of binary search is not exact lookup. It is lower bound. Given a sorted sequence and a target value, a lower-bound search returns the first position whose value is greater than or equal to the target. This operation appears in databases, search engines, interval systems, scheduling software, order books, and indexing structures because it identifies where a value belongs, regardless of whether...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.5 Monotone Predicates

7.5 Monotone Predicates Binary search does not fundamentally require sorted data. What binary search actually requires is a monotone predicate. This observation is one of the most important ideas in algorithm design because it explains why binary search appears in problems involving scheduling, optimization, geometry, networking, manufacturing, databases, and machine learning despite the absence of a sorted array. Once you learn to identify monotone predicates, binary search becomes a general-purpose...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.9 Interval Search

7.9 Interval Search Many search problems involve ranges rather than individual values. A database query may ask for all orders placed between two timestamps. A monitoring system may need all measurements within a temperature range. A search engine may retrieve documents whose scores fall between two thresholds. In each case, the objective is not to locate a single value but to identify a contiguous interval of matching records. A common...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.13 Tree Rotations

7.13 Tree Rotations Tree rotations are the primitive operation behind many balanced binary search trees. AVL trees, red-black trees, treaps, splay trees, and several other ordered structures all use rotations to repair shape while preserving key order. A rotation changes parent-child relationships among a small number of nodes. It does not change the sorted order of the keys. This distinction is critical. A rotation modifies structure, not meaning. The tree...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 7. Binary Search and Ordered Data ›

7.19 Range Queries

7.19 Range Queries A range query asks for information about a contiguous region of ordered data. Sometimes the query returns the elements themselves. More often, it returns an aggregate: a count, sum, minimum, maximum, average, or other summary over a range. Examples: How many values lie between 100 and 500? What is the sum of sales from day 20 to day 30? What is the minimum latency between timestamps t1...
algorithms binary-search ordered-data Jun 1, 2026
Programming › Algorithm Cookbook ›

Chapter 7. Binary Search and Ordered Data

Chapter 7. Binary Search and Ordered Data Binary search is one of the most deceptively simple ideas in computer science. Given a sorted array and a target, you repeatedly cut the search space in half by comparing the target with the middle element. Each comparison eliminates half the remaining candidates, so the algorithm terminates in $O(\log n)$ steps. The simplicity is real — the code is short — but the...
algorithms binary-search ordered-data trees Jun 1, 2026
Wiki › Algorithms › 01. Searching and Sorting › 12. Specialized Search and Sorted-Order Procedures ›

Learned Index Search

Learned Index Search Learned index search treats an ordered index as a prediction problem. Given a key, a model estimates the position where that key should appear in sorted data. The algorithm then corrects the estimate by searching a small range around the predicted position. The main idea is that a sorted array defines a cumulative distribution function from key to position. If this function is predictable, a model can...
algorithms searching learned-index ordered-data indexing
Wiki › Algorithms › 01. Searching and Sorting › 12. Specialized Search and Sorted-Order Procedures ›

Recursive Model Index Search

Recursive Model Index Search Recursive model index search uses several learned models arranged as a hierarchy. A top model selects a lower model, and the lower model predicts the likely position of a key in sorted data. The final prediction is then corrected by searching inside a bounded local range. This is the main search procedure behind a recursive model index, often shortened to RMI. It replaces part of a...
algorithms searching learned-index recursive-model-index ordered-data