Playground Component
Interpolation Search
Visualizer
Visualize Interpolation Search as it estimates likely target positions in a sorted, evenly distributed array.
Interpolation Search Visualizer
Status
Idle
Low
-
Pos
-
High
-
Comparisons
0
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>Interpolation 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.low{border:2px solid #4ea8ff}
.cell.high{border:2px solid #ff6b6b}
.cell.pos{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>Interpolation 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>Low</h4><p id="low">-</p></div>
<div class="stat-box"><h4>Pos</h4><p id="pos">-</p></div>
<div class="stat-box"><h4>High</h4><p id="high">-</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,low=-1,pos=-1,high=-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===low)classes.push("low");
if(index===high)classes.push("high");
if(index===pos)classes.push("pos");
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 setLow(value){low=value;setMarker("low",value);renderArray()}
function setHigh(value){high=value;setMarker("high",value);renderArray()}
function setPos(value){pos=value;setMarker("pos",value);renderArray()}
function clearMarkers(){setLow(-1);setPos(-1);setHigh(-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 interpolationSearch(){
if(searching)return;
const target=Number(targetInput.value);
if(Number.isNaN(target)||targetInput.value==="")return;
searching=true;resetStates();clearMarkers();setComparisons(0);setStatus("Estimating...");syncTarget();
let l=0,h=array.length-1,comps=0;
while(l<=h&&target>=array[l].value&&target<=array[h].value){
let estimate=l;
if(array[h].value!==array[l].value){estimate=l+Math.floor(((target-array[l].value)*(h-l))/(array[h].value-array[l].value))}
estimate=Math.max(l,Math.min(h,estimate));
setLow(l);setHigh(h);setPos(estimate);setRangeState(l,h,"range");setCellState(estimate,"checking");
comps++;setComparisons(comps);
await sleep(speedLevels[speedIndex].delay);
if(array[estimate].value===target){setCellState(estimate,"found");setStatus("Found!");searching=false;return}
if(array[estimate].value<target){setRangeState(l,estimate,"discarded");l=estimate+1}
else{setRangeState(estimate,h,"discarded");h=estimate-1}
await sleep(speedLevels[speedIndex].delay);
}
clearMarkers();setStatus("Not Found");searching=false;
}
document.getElementById("randomizeBtn").addEventListener("click",randomize);
document.getElementById("searchBtn").addEventListener("click",interpolationSearch);
speedBtn.addEventListener("click",toggleSpeed);
targetInput.addEventListener("input",syncTarget);
randomize();
</script>
</body>
</html>
About this Component
Interpolation Search is a searching algorithm for sorted numeric data. Instead of always checking the middle element, it estimates where the target should be based on the values at the current low and high positions. When values are evenly distributed, this estimate can jump very close to the target. This interactive visualization shows how the probe position is calculated, how the search range shrinks, and why the algorithm performs best when the data is sorted and roughly uniform. Interpolation Search has an average-case time complexity of O(log log n) for uniformly distributed data, but its worst-case time complexity can degrade to O(n) when values are unevenly distributed. It uses O(1) extra space in its iterative form and is best suited for sorted numeric arrays.
Explore More Components
Discover more components from the Playground.
