Binary search

이진 탐색

Compare the midpoint of a sorted range and discard half at each step.

···
html
<div class="v"><header><b>BINARY SEARCH</b><span id="state"></span></header><main><div class="nums" id="nums"></div><div class="target">target <b>7</b></div></main><footer>halve the range</footer></div>
css
.v{width:min(92vw,660px);height:min(86vh,310px);box-sizing:border-box;padding:clamp(9px,2.5vmin,18px);border:1px solid var(--line);border-radius:14px;background:var(--surface);display:flex;flex-direction:column;gap:7px;color:var(--fg);font:500 clamp(15px,4.5vmin,19px)/1.25 var(--font-sans, sans-serif)}.v header,.v footer{display:flex;justify-content:space-between;align-items:center;gap:8px;white-space:nowrap}.v header b{color:var(--accent);font-size:.9em}.v header span,.v footer{color:var(--muted);font-size:.82em}.v main{flex:1;min-height:0;position:relative;overflow:hidden}.v .mono{font-family:ui-monospace,SFMono-Regular,Consolas,monospace}.v .active{background:var(--accent)!important;color:var(--bg)!important;border-color:var(--accent)!important}.v .muted{opacity:.45} .nums{height:68%;display:flex;align-items:center;justify-content:center;gap:3px}.nums i{font-style:normal;flex:1;max-width:42px;padding:12px 0;border:1px solid var(--line);border-radius:7px;text-align:center;transition:opacity .25s,background .25s}.target{text-align:center;color:var(--muted)}.target b{color:var(--accent)}
js
let lo=0,hi=8;const nums=[1,2,3,4,5,6,7,8,9],box=document.getElementById("nums");function step(){if(lo>hi){lo=0;hi=8}const mid=Math.floor((lo+hi)/2);box.replaceChildren(...nums.map((n,i)=>{let x=document.createElement("i");x.textContent=n;x.className=(i<lo||i>hi?"muted ":"")+(i===mid?"active":"");return x}));document.getElementById("state").textContent="middle="+nums[mid];if(nums[mid]<7)lo=mid+1;else if(nums[mid]>7)hi=mid-1;else{lo=10}}step();setInterval(step,900)

Binary search compares a target with the middle item of a sorted array. It discards the half that cannot contain the target.

The search range halves at each step, so the number of steps grows logarithmically. Applying it to unsorted data can miss an existing value.

When to use

Use it to find a value or boundary in sorted data.

Open as page ↗