[정글 알고리즘] - [하] -백준 1920번 실버 IV - 이분탐색(Binary Search) - 수 찾기

 

 

정렬된 배열에서 특정 수의 존재 여부를 이분탐색(Binary Search)으로 O(log N)에 찾는 문제입니다.
핵심: left > right가 되면 탐색 실패(0 반환), 중간값과 비교해 범위를 절반씩 줄입니다.

📋 문제 정보

항목	내용
문제 번호	백준 1920번
난이도	🟢 실버 IV
알고리즘	이분탐색, 정렬
입력	1행: N (1 ≤ N ≤ 100,000) 2행: N개 정수 3행: M (1 ≤ M ≤ 100,000) 4행: 찾을 M개 정수
출력	M줄: 존재하면 1, 없으면 0
정수 범위	-2³¹ 이상 2³¹ 미만 (음수 포함)

💡 핵심 아이디어

정렬된 배열에서 탐색 범위를 매번 절반으로 줄입니다.

단계	조건	동작
①	left > right	탐색 실패 → 0 반환
②	j == num_list[mid]	탐색 성공 → 1 반환
③	j > num_list[mid]	오른쪽 절반 탐색 → search(mid+1, right)
④	j < num_list[mid]	왼쪽 절반 탐색 → search(left, mid-1)

🔍 이분탐색 시각화

배열: [1, 2, 3, 4, 5] (정렬 후)  |  찾는 값: 3

인덱스	0	1	2	3	4
값	1	2	3	4	5

호출	left	right	mid	num_list[mid]	비교 (j=3)	결과
1차	0	4	2	3	3 == 3	return 1 ✅

찾는 값: 7 (없는 경우)

호출	left	right	mid	num_list[mid]	비교 (j=7)	다음 호출
1차	0	4	2	3	7 > 3	search(3, 4)
2차	3	4	3	4	7 > 4	search(4, 4)
3차	4	4	4	5	7 > 5	search(5, 4)
4차	5	4	—	—	left > right	return 0 ❌

❓ 왜 먼저 정렬해야 하는가?

이분탐색은 반드시 정렬된 배열에서만 동작합니다.

정렬 전 (이분탐색 불가)	정렬 후 (이분탐색 가능)
[4, 1, 5, 2, 3] mid=5, 찾는값=3 3 < 5 → 왼쪽 탐색 ❌ 하지만 3은 오른쪽에 있음!	[1, 2, 3, 4, 5] mid=3, 찾는값=3 3 == 3 → ✅ 즉시 찾음

✅ 최종 풀이 코드

# 이분탐색 - 수 찾기 (백준 실버4)
# 문제 링크: https://www.acmicpc.net/problem/1920
import sys
input = sys.stdin.readline

n = int(input())
num_list = list(map(int, input().split()))
num_list.sort()                 # 이분탐색 전 반드시 정렬!

def search(left, right):
    if left > right:             # 탐색 범위 소진 → 없음
        return 0

    mid = (left + right) // 2   # 중간 인덱스

    if j == num_list[mid]:       # 찾았다!
        return 1
    elif j > num_list[mid]:      # 오른쪽 절반 탐색
        return search(mid + 1, right)
    else:                        # 왼쪽 절반 탐색
        return search(left, mid - 1)

m = int(input())
targets = list(map(int, input().split()))

for j in targets:
    print(search(0, n - 1))

⏱️ 시간복잡도

단계	복잡도	설명
정렬	O(N log N)	한 번만 수행
탐색 1회	O(log N)	매 단계 절반으로 범위 감소
전체	O(N log N + M log N)	N=M=100,000 → 약 1,700,000 연산 → 통과

🏁 핵심 정리

포인트	내용
📌	정렬 필수 — 이분탐색은 정렬된 배열에서만 올바르게 동작
🔁	기저 조건 — left > right이면 탐색 실패(return 0)
✂️	절반씩 감소 — 크면 오른쪽(mid+1), 작으면 왼쪽(mid-1)
⏱️	선형탐색 O(N) → 이분탐색 O(log N)