Algorithm Guidecomplexity: O(log₃ n)

Ternary Search

Splits the range into thirds and uses two midpoints (mid1, mid2) to discriminate three sections at once. Its recursion is shallower than binary search but it does more comparisons per step, so in practice it's mainly used to find the extremum of a unimodal function.

01Ternary Search

Explore How It Works

Starting ternary search. Split the range into thirds, compare two points at once, and keep the one section that can hold the target.

Splitting ten slots into thirds puts the two boundaries at index 3 and 6. Check both at once.

The boundary values are 34 and 67. 45 falls between them, so keep the middle section and drop both sides.

Repeat on the two remaining slots. The boundaries are index 4 and 5.

The front boundary holds 45 — a match, after splitting the range twice.

Search complete · 45 sits at index 4. Two comparisons per split make it slower than binary search in practice; it is mainly used to find the extremum of a unimodal function.

Live Python

# target: 45

1def ternary_search(arr, low, high, target):

# low: 0

2 if low > high:

# high: 9

3 return -1

4 mid1 = low + (high - low) // 3

5 mid2 = high - (high - low) // 3

6 if arr[mid1] == target:

7 return mid1

8 if arr[mid2] == target:

9 return mid2

10 if target < arr[mid1]:

11 return ternary_search(arr, low, mid1 - 1, target)

12 elif target > arr[mid2]:

13 return ternary_search(arr, mid2 + 1, high, target)

14 else:

15 return ternary_search(arr, mid1 + 1, mid2 - 1, target)

1 / 6

02 Understand It Simply

For Everyone

🔑How It Works

Splits the range into three, checks two points and discards one third. Used to find the extremum of a unimodal function.

💡In Plain Words

Divides the range into thirds and narrows using two points.

Used less for sorted search and more for finding the extremum of a convex (unimodal) function.

📍Where It's Used

–Finding the optimum of a unimodal function

03 Python Implementation

A clean, readable reference implementation of the core logic of Ternary Search.

core_implementation.py

def ternary_search(arr, low, high, target):
    if low > high:
        return -1
    mid1 = low + (high - low) // 3
    mid2 = high - (high - low) // 3
    if arr[mid1] == target:
        return mid1
    if arr[mid2] == target:
        return mid2
    if target < arr[mid1]:
        return ternary_search(arr, low, mid1 - 1, target)
    elif target > arr[mid2]:
        return ternary_search(arr, mid2 + 1, high, target)
    else:
        return ternary_search(arr, mid1 + 1, mid2 - 1, target)