1. 순차·이진 탐색

← 전체 목차 이 단원 목차

🎮 이 단원이 게임에서 쓰이는 곳 (언더테일·RPG)

순차·이진 탐색 = 아이템/데이터 찾기에 씁니다. "이름으로 아이템 ID 찾기", "정렬된 테이블에서 스킬 번호로 이름 찾기"처럼요. 정렬된 데이터가 있으면 이진 탐색으로 빠르게 찾을 수 있어요.

순차 탐색

첫 번째 칸부터 차례대로 "이거 내가 찾는 값이야?" 하고 비교하는 방법이에요. 찾을 때까지 또는 끝까지 가면 끝입니다. 정렬이 안 되어 있어도 쓸 수 있어요. 데이터가 n개면 최대 n번 비교해요.

이진 탐색(Binary Search, 바이너리 서치)

자료가 이미 오름차순(또는 내림차순)으로 정렬되어 있을 때만 쓸 수 있어요. 가운데 값을 보고, 찾는 값이 더 크면 오른쪽 절반만, 더 작으면 왼쪽 절반만 다시 봐요. 반씩 버리니까 훨씬 빨라요.

시험에 "비교 횟수", "첫 번째로 비교하는 값", "중간 인덱스" 같은 게 자주 나와요.

📌 이론(알고리즘 단계) ↔ 파이썬 함수

이진 탐색 가운데 인덱스 → mid = (left + right) // 2 | 오른쪽 절반으로 좁히기 → left = mid + 1 (왼쪽은 right = mid - 1)

대응 이진 탐색은 "현재 구간의 가운데 인덱스"를 구하고, 찾는 값과 비교해서 왼쪽/오른쪽 절반 중 하나만 남기며 반복해요.

(left + right) // 2: 정수 나눗셈 //로 가운데 인덱스를 구해요. 예: left=0, right=6이면 (0+6)//2 = 3. 실수 나눗셈(/)이 아니라 //를 쓰는 이유는 인덱스는 항상 정수여야 하기 때문이에요.
리스트[mid]: mid번째 칸의 값이에요. 이 값과 찾는 target을 비교해서 "같으면 찾음", "target이 더 크면 오른쪽 절반", "더 작으면 왼쪽 절반"으로 구간을 좁혀요.
left = mid + 1 (또는 right = mid - 1): target이 arr[mid]보다 크면 "오른쪽 절반"만 보면 되므로, 구간의 왼쪽 끝을 mid 다음으로 옮겨요: left = mid + 1. 반대로 target이 더 작으면 right = mid - 1로 오른쪽 끝을 줄여요.

왜 이렇게 쓰나요? 이진 탐색의 핵심은 "매번 구간의 가운데를 보고 절반을 버리는 것"이에요. 가운데 인덱스를 정수로 구하는 //, 구간을 좁히는 left/right 갱신이 그대로 코드에 반영됩니다.

📌 파이썬 while·if 기초

while 루프 while 조건:은 "조건이 참인 동안" 아래 블록을 반복해요. 이진 탐색에서는 while left <= right:로 "구간이 남아 있는 한" 계속 가운데를 보며 좁혀요. 들여쓰기된 줄이 반복할 블록이에요.

if / else if 조건: 다음에 들여쓰기한 줄은 "조건이 참일 때만" 실행돼요. else:는 "위 if가 거짓일 때" 실행할 블록이에요. if arr[mid] == target:이면 "가운데 값이 찾는 값이면" 그때 break로 루프를 끝내요.

가운데 인덱스 mid = ? target이 더 크면 left = ?

mid = _____ left = _____

첫 빈칸: 두 번째:

🐍 파이썬 (바로 실행)

🟨 자바스크립트로 확인

var arr = [2, 5, 8, 12, 16, 23, 38];
var target = 12, left = 0, right = arr.length - 1;
while (left <= right) {
  var mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) { console.log('찾음! 인덱스:', mid); break; }
  if (arr[mid] < target) left = mid + 1;
  else right = mid - 1;
}
if (left > right) console.log('없음');

🔄 유사 알고리즘 비교: 순차 탐색 vs 이진 탐색

둘 다 "찾는 값의 위치"를 구하지만, 전제 조건과 비교 횟수가 달라요. 아래 표로 차이를 비교해 보세요.

구분	순차 탐색	이진 탐색
전제 조건	정렬 필요 없음. 아무 순서로 되어 있어도 됨.	자료가 이미 오름차순(또는 내림차순) 정렬되어 있어야 함.
방법	첫 번째 칸부터 차례대로 target과 비교. 같으면 종료, 아니면 다음 칸.	현재 구간의 가운데 값과 비교. target이 더 크면 오른쪽 절반만, 더 작으면 왼쪽 절반만 남기고 반복.
최대 비교 횟수 (n개일 때)	최악 n번 (맨 끝에 있거나 없을 때)	최악 약 log₂ n번 (반씩 버리므로 훨씬 적음)
쓰는 연산	인덱스 0, 1, 2, … 순으로 증가하며 `arr[i] == target` 비교	`mid = (left+right)//2`, `arr[mid]`와 비교, `left = mid+1` 또는 `right = mid-1`로 구간 좁히기
공통점	모두 배열(리스트)에서 특정 값을 찾음. "찾음/없음"과 "인덱스"를 구할 수 있음.

문제 및 해설

📋 기출 유형

[10, 20, 30, 40, 50, 60, 70]에서 40을 이진 탐색할 때, 첫 번째로 비교하는 값은?

정답: 40

풀이 단계

이진 탐색은 매번 "현재 구간의 가운데 값"과 찾는 값을 비교합니다. 첫 번째 비교 때 현재 구간은 전체 배열이에요.
인덱스 0~6(7개)일 때 가운데 인덱스는 (0+6)÷2 = 3. 세 번째 칸(인덱스 3)의 값은 40입니다.
따라서 첫 번째로 비교하는 값은 40이에요. 40을 찾는 문제이므로 첫 비교에서 바로 찾게 됩니다.

가운데는 어떻게 구하나요? (왼쪽 인덱스 + 오른쪽 인덱스) ÷ 2 의 정수 부분, 즉 (left+right)//2 로 구합니다. 7개면 (0+6)//2 = 3.

한 줄 요약 이진 탐색 첫 비교 = "현재 구간의 가운데 값". 7개 배열이면 인덱스 3 = 네 번째 값. 더 많은 예제 →

문제 및 답 확인

위 배열에서 25를 이진 탐색할 때, 첫 번째 비교 후 다음에 볼 구간(인덱스 범위)은?

답 보기

정답: 인덱스 0~2 (값으로는 10, 20, 30)

풀이 첫 비교는 가운데(인덱스 3) 값 40과 25를 비교합니다. 25 < 40이므로 "25는 40보다 작다" → 왼쪽 절반에 있어요. 따라서 다음에 볼 구간은 인덱스 0~2(10, 20, 30)입니다. 이진 탐색은 "비교한 값보다 작으면 왼쪽, 크면 오른쪽" 절반만 남겨서 반복해요.

도전과제

풀어 본 뒤 정답을 펼쳐 확인하세요.

도전 1. 정렬된 배열 [10, 20, 30, 40, 50]에서 35를 이진 탐색할 때, 비교하는 값의 순서는? (가운데부터)

정답 보기

정답: 30 → 40 → (없음)

첫 비교: mid=2, 30. 35>30 → 오른쪽 절반 [40,50]. 두 번째: mid=3, 40. 35<40 → 왼쪽 절반 없음(구간 3~2로 만료). 35는 배열에 없으므로 "찾지 못함"이에요. 게임에서 ID 35번 아이템이 테이블에 없을 때와 같은 경우예요.

도전 2. "정렬되지 않은 인벤토리"에서 특정 아이템을 찾을 때 순차 탐색과 이진 탐색 중 뭘 써야 하나요? 그 이유는?

정답 보기

정답: 순차 탐색

이유: 이진 탐색은 "정렬된" 데이터에서만 동작해요. 정렬되지 않았으면 "가운데 값"을 봐도 왼쪽/오른쪽에 찾는 값이 있다고 확신할 수 없어요. 정렬되지 않은 목록에서는 처음부터 끝까지 하나씩 보는 순차 탐색을 써야 해요.

위 실습은 이 강의(이진 탐색)에서 배운 가운데 인덱스 (left+right)//2, 구간 좁히기 left=mid+1/right=mid-1을 쓰는 예제입니다. 손으로 해보려면 실습: 탐색 (손으로 하기).