Overview
Saddleback Search is a search method that uses ordering, indexing, predicates, or distance bounds to eliminate candidates. It is a good fit when the collection has enough structure to avoid checking every candidate.
CoreSource checked
Saddleback Search
Saddleback Search locates items by exploiting structure in the collection or search space.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Searching
- Difficulty
- Intermediate
- Family
- Search
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
Core Concepts
candidate pruningcomparison rulesearch intervalcandidate setquery comparisonelimination
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(log n)
Worst
O(n)
Space
O(1)
When to Use
- Use Saddleback Search when the collection has the ordering, metric, or index structure it needs.
- Use it when setup or indexing cost is repaid by faster lookup.
When Not to Use
- Avoid when the data lacks the ordering, index, predicate, or metric structure the method needs.
- Avoid when setup costs exceed savings for a small one-off search.
What It Does
- Narrows candidate items
- Uses ordering, indexing, or distance tests
- Returns the best matching position or item
Use Cases
- Lookup in ordered data
- Nearest-neighbor search
- Predicate search
Inputs
- Collection or search space
- Target value or predicate
- Ordering or distance rule
Outputs
- Found item or position
- Nearest candidate
- Not-found result
Key Formulas (1)
Matrix move rule
if value > target move left, else move down
if value > target move left, else move downUses sorted rows and columns to eliminate a row or column each step.
Pseudocode
- 1.Initialize the candidate range, index, or frontier
- 2.Evaluate the target, predicate, or distance rule
- 3.Discard candidates that cannot improve the result
- 4.Repeat until the target or best candidate is found
- 5.Return the position, value, or not-found result
Canonical Example
- Input
- items = [1, 3, 5, 8], target or predicate = 5
- Output
- matching position or best candidate
- Explanation
- Saddleback Search eliminates candidates until it finds the target or proves that no better candidate remains.
Implementation Notes
- Assert sorted, indexed, or metric preconditions where possible.
- Test empty, single-item, duplicate, and boundary target cases.
- Search algorithms should define both success and failure semantics.
Common Pitfalls
- Using the method on unsorted or unindexed data silently breaks assumptions.
- Off-by-one bounds errors can skip valid candidates.
- Off-by-one bounds, duplicates, and missing-target behavior should be specified before implementation.
Interactive Mechanism Walkthrough
Indexed Interval & Boundary ProbeShow candidate regions shrinking as comparisons or distance tests eliminate options.
Target key: 41low=0, mid=4, high=9
4[0]
9[1]
15[2]
22[3]
27[4]
34[5]
41[6]
49[7]
58[8]
63[9]
Step 1 of 5: Initialize the candidate range, index, or frontier
searchNotes
Saddleback Search operates in O(log n) time and O(1) space within the Search family. Key governing relation: if value > target move left, else move down. Often compared with Binary Search and Linear Search.
Sources (1)
What each reference supports for this entry.
The Art of Computer Programming, Volume 3
BookSorting and searching reference covering Saddleback Search comparison model, probe strategy, network structure, or pass schedule.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageConceptual neighborBinary Search
Saddleback Search and Binary Search address nearby searching problems but make different implementation tradeoffs.
Related Algorithms
Tags
Search