정보·컴퓨팅 · 알고리즘 탐구 / 원리와 탐구
선형 탐색과 이진 탐색 실험 해설
정렬된 목록에서 후보 범위와 현재 비교 위치가 바뀌는 모습을 봐요.
어떤 원리인가요?
이진 탐색은 비교할 때마다 후보 범위를 절반으로 줄여요.
핵심 관계
binary steps ≤ ⌊log₂n⌋ + 1
이렇게 관찰해 보세요
- 정렬된 목록에서 후보 범위와 현재 비교 위치가 바뀌는 모습을 봐요.
- 기준 조건 세 가지를 각각 실행하고 측정값을 기록해요.
- 한 변수만 바꾸어 기준 기록과 결과를 비교해요.
결과를 읽는 기준
이진 탐색에 필요한 조건은?
목록이 정렬돼 있어요 · 이진 탐색은 비교할 때마다 후보 범위를 절반으로 줄여요.
모형의 범위와 한계
중복 없는 정렬된 정수 목록이에요. 선형 탐색도 같은 목록을 사용해요.