What is Ternary Search?

Ternary Search is a searching algorithm that divides a sorted range into three parts using two midpoints, then continues in the section that may contain the target.

What is the time complexity of Ternary Search?

Ternary Search runs in O(1) time in the best case and O(log n) time in the average and worst cases.

Does Ternary Search require sorted data?

Yes. For array searching, Ternary Search requires sorted data so it can safely discard parts of the range.

How much extra space does Ternary Search use?

Iterative Ternary Search uses O(1) extra space because it only stores boundary indexes and midpoint values.

Why should I learn Ternary Search?

Ternary Search helps explain divide-and-conquer searching and is also an important idea for optimization problems on unimodal functions.

Playground Component

Ternary Search
Visualizer

Visualize Ternary Search as it splits a sorted range into three parts and decides which section can contain the target.

Ternary Search Visualizer

Status

Idle

Left

Mid 1

Mid 2

Right

Comparisons

Target

Copy Code


<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Ternary Search Visualizer</title>
  <style>
    :root{--bg:#090909;--panel:#111111;--gold:#f4c430;--gold-dark:#b88700;--text:#f5f5f5;--border:#2f2f2f}
    *{box-sizing:border-box}
    body{margin:0;background:#090909}
    .search-visualizer{min-height:100vh;padding:40px;background:radial-gradient(circle at top,#1a1505 0%,#090909 40%);color:var(--text);font-family:'Poppins',Arial,sans-serif}
    .search-visualizer h2{text-align:center;font-size:3rem;color:var(--gold);margin:0 0 35px}
    .controls{display:flex;justify-content:center;gap:15px;flex-wrap:wrap;margin-bottom:35px}
    .controls input{width:160px;padding:14px;border-radius:12px;border:1px solid #555;background:#151515;color:var(--gold);text-align:center;font-size:16px;outline:none}
    .controls input:focus{border-color:var(--gold)}
    .controls button{padding:14px 22px;border:none;border-radius:12px;cursor:pointer;font-weight:600;font-size:15px;background:linear-gradient(180deg,#ffd54d,#d9a900);color:#111;transition:.25s}
    .controls button:hover{transform:translateY(-2px)}
    .stats{width:100%;max-width:900px;margin:auto auto 40px;display:grid;grid-template-columns:repeat(3,1fr);gap:18px}
    .stat-box{background:#151515;border:1px solid #2b2b2b;border-radius:14px;padding:18px;text-align:center}
    .stat-box h4{margin:0;color:#999;font-size:.9rem}
    .stat-box p{margin:8px 0 0;color:var(--gold);font-size:1.4rem;font-weight:bold}
    .array{display:flex;justify-content:center;flex-wrap:wrap;gap:14px}
    .cell{width:72px;height:72px;border-radius:14px;background:#171717;border:2px solid #2c2c2c;display:flex;flex-direction:column;justify-content:center;align-items:center;transition:.25s}
    .cell div{font-size:1.3rem;font-weight:700}
    .cell small{margin-top:5px;color:#999;font-size:.72rem}
    .cell.default{background:#171717}
    .cell.range{background:#241d08;border-color:#6f560f}
    .cell.checking{background:#ffb000;color:black;border-color:#ffd54d;transform:translateY(-8px) scale(1.05);box-shadow:0 0 20px rgba(255,193,7,.45)}
    .cell.found{background:#25c05a;color:white;border-color:#43e97b;transform:scale(1.12);box-shadow:0 0 22px rgba(37,192,90,.5)}
    .cell.discarded{opacity:.28}
    .cell.left{border:2px solid #4ea8ff}
    .cell.right{border:2px solid #ff6b6b}
    .cell.mid{background:#b26dff;border-color:#d7b3ff}
    @media(max-width:768px){.search-visualizer{padding:20px}.search-visualizer h2{font-size:2rem}.stats{grid-template-columns:repeat(2,1fr)}.cell{width:58px;height:58px}.cell div{font-size:1rem}}
  </style>
</head>
<body>
  <div class="search-visualizer">
    <h2>Ternary Search Visualizer</h2>
    <div class="controls">
      <button id="randomizeBtn">Randomize</button>
      <input id="targetInput" type="number" placeholder="Target">
      <button id="searchBtn">Search</button>
      <button id="speedBtn">Speed: Normal</button>
    </div>
    <div class="stats">
      <div class="stat-box"><h4>Status</h4><p id="status">Idle</p></div>
      <div class="stat-box"><h4>Left</h4><p id="left">-</p></div>
      <div class="stat-box"><h4>Mid 1</h4><p id="mid1">-</p></div>
      <div class="stat-box"><h4>Mid 2</h4><p id="mid2">-</p></div>
      <div class="stat-box"><h4>Right</h4><p id="right">-</p></div>
      <div class="stat-box"><h4>Comparisons</h4><p id="comparisons">0</p></div>
      <div class="stat-box"><h4>Target</h4><p id="targetValue">-</p></div>
    </div>
    <div id="array" class="array"></div>
  </div>

  <script>
    const speedLevels=[{name:"Very Slow",delay:500},{name:"Slow",delay:200},{name:"Normal",delay:100},{name:"Fast",delay:50},{name:"Very Fast",delay:10}];
    let array=[],speedIndex=2,searching=false,left=-1,mid1=-1,mid2=-1,right=-1;
    const arrayEl=document.getElementById("array"),targetInput=document.getElementById("targetInput"),speedBtn=document.getElementById("speedBtn");
    function sleep(ms){return new Promise(resolve=>setTimeout(resolve,ms))}
    function createSortedArray(){const used=new Set(),arr=[];while(arr.length<48){const value=Math.floor(Math.random()*100)+10;if(!used.has(value)){used.add(value);arr.push({value,state:"default"})}}return arr.sort((a,b)=>a.value-b.value)}
    function setStatus(value){document.getElementById("status").textContent=value}
    function setMarker(id,value){document.getElementById(id).textContent=value===-1?"-":value}
    function setComparisons(value){document.getElementById("comparisons").textContent=value}
    function syncTarget(){document.getElementById("targetValue").textContent=targetInput.value||"-"}
    function renderArray(){
      arrayEl.innerHTML="";
      array.forEach((item,index)=>{
        const classes=["cell"];
        if(index===left)classes.push("left");
        if(index===right)classes.push("right");
        if(index===mid1||index===mid2)classes.push("mid");
        classes.push(item.state);
        const cell=document.createElement("div");
        cell.className=classes.join(" ");
        cell.innerHTML=`<div>${item.value}</div><small>Index ${index}</small>`;
        arrayEl.appendChild(cell);
      });
    }
    function setLeft(value){left=value;setMarker("left",value);renderArray()}
    function setRight(value){right=value;setMarker("right",value);renderArray()}
    function setMid1(value){mid1=value;setMarker("mid1",value);renderArray()}
    function setMid2(value){mid2=value;setMarker("mid2",value);renderArray()}
    function clearMarkers(){setLeft(-1);setMid1(-1);setMid2(-1);setRight(-1)}
    function setCellState(index,state){if(array[index]){array[index].state=state;renderArray()}}
    function setRangeState(start,end,state){array=array.map((item,index)=>index>=start&&index<=end?{...item,state}:item);renderArray()}
    function resetStates(){array=array.map(item=>({...item,state:"default"}));renderArray()}
    function randomize(){if(searching)return;array=createSortedArray();targetInput.value="";clearMarkers();setComparisons(0);setStatus("Idle");syncTarget();renderArray()}
    function toggleSpeed(){speedIndex=(speedIndex+1)%speedLevels.length;speedBtn.textContent=`Speed: ${speedLevels[speedIndex].name}`}
    async function ternarySearch(){
      if(searching)return;
      const target=Number(targetInput.value);
      if(Number.isNaN(target)||targetInput.value==="")return;
      searching=true;resetStates();clearMarkers();setComparisons(0);setStatus("Searching...");syncTarget();
      let l=0,r=array.length-1,comps=0;
      while(l<=r){
        const third=Math.floor((r-l)/3),m1=l+third,m2=r-third;
        setLeft(l);setRight(r);setMid1(m1);setMid2(m2);setRangeState(l,r,"range");setCellState(m1,"checking");setCellState(m2,"checking");
        comps+=m1===m2?1:2;setComparisons(comps);
        await sleep(speedLevels[speedIndex].delay);
        if(array[m1].value===target){setCellState(m1,"found");setStatus("Found!");searching=false;return}
        if(array[m2].value===target){setCellState(m2,"found");setStatus("Found!");searching=false;return}
        if(target<array[m1].value){setRangeState(m1,r,"discarded");r=m1-1}
        else if(target>array[m2].value){setRangeState(l,m2,"discarded");l=m2+1}
        else{setRangeState(l,m1,"discarded");setRangeState(m2,r,"discarded");l=m1+1;r=m2-1}
        await sleep(speedLevels[speedIndex].delay);
      }
      clearMarkers();setStatus("Not Found");searching=false;
    }
    document.getElementById("randomizeBtn").addEventListener("click",randomize);
    document.getElementById("searchBtn").addEventListener("click",ternarySearch);
    speedBtn.addEventListener("click",toggleSpeed);
    targetInput.addEventListener("input",syncTarget);
    randomize();
  </script>
</body>
</html>

About this Component

Ternary Search is a divide-and-conquer searching algorithm that splits a sorted search range into three parts using two midpoints. By comparing the target with those midpoint values, it eliminates one or two sections and continues searching only where the target can still exist. This interactive visualization shows the low, first-mid, second-mid, and high boundaries so you can follow how the candidate range changes after each comparison. For searching in a sorted array, Ternary Search has a best-case time complexity of O(1) and an average and worst-case time complexity of O(log n). It uses O(1) extra space in an iterative version. Although it has logarithmic complexity, Binary Search is often preferred for arrays because it needs fewer comparisons per step.