정렬된 배열에서 이진 탐색의 평균·최악 시간복잡도 차수는?

컴퓨터 일반 및 정보설비 기준 · Binary Search에서 반복해서 확인해야 할 핵심 개념을 문제와 해설로 정리했습니다.

5과목 Binary Search 문제 모음 표준

보기

1. O(1)

2. O(log n)

3. O(n)

4. O(n²)

정답 2번

이진 탐색은 매 비교마다 탐색 범위를 절반으로 줄이므로 로그 시간에 동작한다. 풀이 근거: n→n/2→n/4 구조를 확인한다. 선지 판별의 기준은 문제에서 제시된 「Binary Search」 조건과 정답 선택지의 기술적 의미가 일치하는지 확인하는 것이다.

풀이 과정

① 요구 조건: 정렬된 배열에서 이진 탐색의 평균·최악 시간복잡도 차수는?
② 핵심 개념: 이진 탐색은 매 비교마다 탐색 범위를 절반으로 줄이므로 로그 시간에 동작한다.
③ 판정·계산: n→n/2→n/4 구조를 확인한다.
④ 오답 구분: 정렬되지 않은 데이터에는 그대로 적용할 수 없다.
⑤ 정답: 2번 「O(log n)」.

오답 함정
정렬되지 않은 데이터에는 그대로 적용할 수 없다.
이 문제의 정답 기준: 이진 탐색은 매 비교마다 탐색 범위를 절반으로 줄이므로 로그 시간에 동작한다.

시험 포인트
Binary search=O(log n).

CBT에서 문제 풀기 Binary Search 문제 모음 5과목 핵심 요약 같은 과목 문제

자료 성격 · 이 문항과 해설은 공개 시험문항을 복제한 자료가 아니라 정보통신기사 학습 범위에 맞춰 K-BOOKS가 직접 작성한 학습용 문항입니다. 법령·고시·기준은 실제 응시 시점의 최신 공식 원문을 다시 확인하세요.