concept · INFO-CS-ADS-121Ternary Search
Ternary search is a searching technique that divides a search interval into three sections using two middle positions. It is used for ordered search spaces and, in a different form, for locating extrema of suitable unimodal functions.
Explanation
Overview
Ternary search is a divide-and-conquer technique that selects two positions inside a search interval and uses their values to eliminate one or more sections of the interval.
Key concepts
name: Core idea; description: The central focus of ternary search is the capability described here: Ternary search is a searching technique that divides a search interval into three sections using two middle positions. It is used for ordered search spaces and, in a different form, for locating extrema of suitable unimodal functions.; name: Problem context; description: Ternary Search is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using ternary search, check its assumptions, input requirements, expected output, and resource constraints.
Time complexity
O(log n) time for discrete ternary search because the remaining interval is reduced by a constant factor, approximately one third, per iteration.
Space complexity
O(1) auxiliary space for an iterative implementation. A recursive version requires additional stack space proportional to the logarithm of the input size.
Example
Consider the sorted array [5, 10, 15, 20, 25, 30, 35, 40, 45] and target 30. The algorithm examines two interior positions, uses their values to identify the relevant third, and repeats until 30 is located.
Pseudocode
TERNARY_SEARCH(A, target):
low = 0
high = length(A) - 1
while low <= high:
third = (high - low) // 3
mid1 = low + third
mid2 = high - third
if A[mid1] == target:
return mid1
if A[mid2] == target:
return mid2
if target < A[mid1]:
high = mid1 - 1
else if target > A[mid2]:
low = mid2 + 1
else:
low = mid1 + 1
high = mid2 - 1
return -1
Advantages
Uses two comparison positions to divide an ordered interval into three sections.; Provides logarithmic search complexity.; Can be adapted to unimodal optimization problems.; Offers an alternative divide-and-conquer strategy.
Example or application
Consider the sorted array [5, 10, 15, 20, 25, 30, 35, 40, 45] and target 30. The algorithm examines two interior positions, uses their values to identify the relevant third, and repeats until 30 is located.
Definition
Ternary search is a divide-and-conquer technique that selects two positions inside a search interval and uses their values to eliminate one or more sections of the interval.
Search Purpose
In its discrete form, ternary search can locate a target in a sorted collection by comparing it with two selected middle elements.
Continuous Optimization Purpose
For a unimodal function, ternary search can narrow an interval containing a maximum or minimum by comparing function values at two interior points. This optimization version is conceptually different from searching for an exact array element.
Prerequisites
Discrete ternary search requires an ordered collection and consistent comparisons. Continuous optimization requires a suitable unimodal function over the interval being examined.
Working Principle
The algorithm divides the current interval into approximately three parts using two middle positions. The comparisons determine which section can contain the target or the desired extremum.
Discrete Algorithm Steps
Set the lower and upper search boundaries.
Calculate two interior positions that divide the interval into approximately three sections.
Compare the target with the elements at those positions.
If either position contains the target, return its index.
Otherwise, use the ordering to eliminate sections that cannot contain the target.
Repeat until the target is found or the interval becomes empty.
Pseudocode
TERNARY_SEARCH(A, target):
low = 0
high = length(A) - 1
while low <= high:
third = (high - low) // 3
mid1 = low + third
mid2 = high - third
if A[mid1] == target:
return mid1
if A[mid2] == target:
return mid2
if target < A[mid1]:
high = mid1 - 1
else if target > A[mid2]:
low = mid2 + 1
else:
low = mid1 + 1
high = mid2 - 1
return -1
Comparison With Binary Search
Binary search divides an interval into two parts and usually performs one main middle comparison per iteration. Ternary search divides it into three parts but generally performs two middle comparisons, so the smaller interval does not automatically make it faster.
Time Complexity
O(log n) time for discrete ternary search because the remaining interval is reduced by a constant factor, approximately one third, per iteration.
Space Complexity
O(1) auxiliary space for an iterative implementation. A recursive version requires additional stack space proportional to the logarithm of the input size.
Optimization Complexity
For continuous optimization, the number of iterations depends on the initial interval width and the desired precision. Repeatedly reducing the interval by a constant fraction produces logarithmic convergence with respect to the required precision.
Advantages
Uses two comparison positions to divide an ordered interval into three sections.
Provides logarithmic search complexity.
Can be adapted to unimodal optimization problems.
Offers an alternative divide-and-conquer strategy.
Limitations
Usually performs more comparisons per iteration than binary search.
Is not generally faster than binary search for ordinary sorted-array lookup.
Requires appropriate ordering or unimodality assumptions.
Incorrect interval elimination can discard the target or optimum.
Common Applications
Educational demonstrations of multi-part divide-and-conquer searching.
Searching in suitable ordered collections.
Finding maxima or minima of unimodal functions.
Numerical optimization over a bounded interval.
Implementation Considerations
The programmer must distinguish discrete element searching from continuous function optimization. The interval updates and stopping conditions are different for these two uses.
Common Errors
Assuming ternary search is always faster than binary search.
Applying the method to data without a valid ordering.
Using a continuous unimodal optimization procedure for an ordinary exact-value lookup.
Incorrectly calculating the two interior positions or updating the interval boundaries.
Key Takeaway
Ternary search reduces a suitable interval into three parts, but its extra comparisons mean it is not automatically preferable to binary search for ordinary sorted-array searching.
Key Concepts
| Name | Description |
|---|
Core idea | The central focus of ternary search is the capability described here: Ternary search is a searching technique that divides a search interval into three sections using two middle positions. It is used for ordered search spaces and, in a different form, for locating extrema of suitable unimodal functions. |
Problem context | Ternary Search is relevant when a computational task requires the behavior or capability described by this topic. |
Correct use | Before using ternary search, check its assumptions, input requirements, expected output, and resource constraints. |
Practice Questions
| Question | Answer |
|---|
What is the main purpose of ternary search? | Ternary search is a searching technique that divides a search interval into three sections using two middle positions. It is used for ordered search spaces and, in a different form, for locating extrema of suitable unimodal functions. |
What should be checked before applying ternary search? | For ternary search, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of ternary search be validated? | Trace a representative ternary search case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Learning Objectives
Explain the central idea and purpose of ternary search.
Identify the assumptions, inputs, and conditions relevant to ternary search.
Evaluate an application of ternary search for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Scienexy Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures