이진 탐색은 정렬된 배열에서 중앙 원소와 목표를 비교합니다. 목표가 더 작으면 오른쪽 절반을, 더 크면 왼쪽 절반을 버립니다.
범위가 매번 반으로 줄어 탐색 단계 수는 로그 형태로 늘어납니다. 정렬되지 않은 데이터에 그대로 적용하면 필요한 값을 놓칠 수 있습니다.
언제 쓰나
정렬된 목록에서 특정 값이나 경계 위치를 찾을 때 씁니다.
이진 탐색
Binary search
정렬된 범위의 가운데 값을 비교해 절반씩 버립니다.
···
<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>.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)}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)