2024 국가직9급 컴퓨터일반 9번 해설 — 이진 탐색
문제
다음 파이썬 코드는 이진 탐색을 이용하여 자연수 데이터를 탐색하는 함수이다. (가), (나)에 들어갈 내용을 바르게 연결한 것은? (단, ds는 오름차순으로 정렬된 중복 없는 자연수 리스트이고, key는 찾고자 하는 값이다) def binary(ds, key): low = 0 high = len(ds) - 1 while low <= high: mid = (low+high) // 2 if key == ds[mid]: return mid elif key < ds[mid]: (가) else: (나) return (가) (나)
- ① high = mid - 1 low = mid - 1
- ② high = mid - 1 low = mid + 1 ← 정답
- ③ high = mid + 1 low = mid - 1
- ④ high = mid + 1 low = mid + 1 컴퓨터일반
선지별 해설
① high = mid - 1 low = mid - 1
이 선지 진술은 틀림(X)
key가 중간값보다 클 때는 오른쪽 구간을 탐색해야 하므로 low를 mid+1로 올려야 한다. low를 mid-1로 줄이면 탐색 범위가 잘못된다.
② high = mid - 1 low = mid + 1
이 선지 진술은 옳음(O)
작은 값은 왼쪽 절반에 있으므로 high를 줄이고, 큰 값은 오른쪽 절반에 있으므로 low를 올린다. 이 갱신식이 표준 이진 탐색의 조건이다.
③ high = mid + 1 low = mid - 1
이 선지 진술은 틀림(X)
key가 중간값보다 작을 때는 high를 mid-1로 줄여 왼쪽을 탐색해야 한다. 두 갱신식이 모두 탐색 방향과 맞지 않는다.
④ high = mid + 1 low = mid + 1 컴퓨터일반
이 선지 진술은 틀림(X)
key가 더 작으면 탐색 범위를 왼쪽으로 좁혀야 하므로 high=mid-1이 되어야 한다. high=mid+1은 범위를 잘못 갱신한다.
핵심 요약 (Q&A)
- Q. 2024 국가직9급 컴퓨터일반 9번의 핵심 쟁점은 무엇인가?
- A. 2024 국가직9급 컴퓨터일반 9번은 이진 탐색에 관한 문항으로, "옳은 것"을 고르는 문제입니다.
- Q. 2024 국가직9급 컴퓨터일반 9번의 정답은?
- A. 정답은 ②번입니다. 작은 값은 왼쪽 절반에 있으므로 high를 줄이고, 큰 값은 오른쪽 절반에 있으므로 low를 올린다. 이 갱신식이 표준 이진 탐색의 조건이다.