Ternary Search Visualizer

Target:

Speed:

SlowFast

Elements:

715

(10)

Mid Points (mid1, mid2)

Boundaries

Target Value

Found

Out of Range

Operation Logs

No operations yet

Algorithm Info

Time Complexity: O(log₃ n) ≈ 0.63 × O(log₂ n)

Space Complexity: O(1) - uses constant extra space

Best Case: O(1) - target is at one of the mid points

Worst Case: O(log₃ n) - target requires full tree traversal

Prerequisite: Array must be sorted in ascending order

How it works: Divides array into three equal parts using two mid points (1/3 and 2/3 positions). Compares target with both mid points and eliminates two-thirds or one-third of array in each iteration.

Advantage: Fewer iterations than binary search but more comparisons per iteration.

When to use: When comparison cost is low and array access cost is high.

Implementation

function ternarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid1 = left + Math.floor((right - left) / 3);
    const mid2 = right - Math.floor((right - left) / 3);
    if (arr[mid1] === target) return mid1;
    if (arr[mid2] === target) return mid2;
    if (target < arr[mid1]) {
      right = mid1 - 1;
    } else if (target > arr[mid2]) {
      left = mid2 + 1;
    } else {
      left = mid1 + 1;
      right = mid2 - 1;
    }
  }
  return -1;
}