이 실험 소개
선형 검색과 이진 검색을 나란히 실행해 같은 대상을 찾습니다. 각 단계에서는 아직 끝나지 않은 각 알고리즘이 한 번씩 비교합니다. 이진 검색은 남아 있는 정렬된 구간의 중간을 확인하고, 선형 검색은 한 번에 한 위치씩 이동합니다. 홀수를 대상으로 선택하면 두 알고리즘 모두 일치하는 값을 찾지 못한 채 종료되는 모습을 볼 수 있습니다.
학습 목표
- 이진 검색에서 후보 구간과 중간 위치 추적하기
- 선형 검색과 이진 검색의 비교 횟수 비교하기
- 이진 검색에 정렬된 데이터가 필요한 이유와 대상이 없을 때 처리하는 방법 설명하기
사용 방법
- 1기본 배열에서 32를 찾으며 비교를 한 번씩 진행합니다.
- 2이진 검색이 끝나는 시점을 확인한 다음, 선형 검색이 끝날 때까지 계속합니다.
- 331과 같은 홀수를 선택합니다. 이진 검색에서 후보 구간이 비는 과정을 살펴봅니다.
- 4배열 길이를 변경하고 마지막 값을 검색합니다. 최악의 경우의 상한을 비교합니다.
모델
가정
- 배열에는 오름차순으로 정렬된 중복 없는 짝수 정수 2, 4, ..., 2n이 들어 있습니다. 인덱스는 0부터 시작합니다.
- 값 비교는 대상 값과 한 번 수행하는 3방향 비교입니다. 인덱스 계산과 반복문 조건 확인은 횟수에 포함하지 않습니다.
- 선형 검색은 대상 값이 없으면 배열 전체를 훑으며, 정렬되어 있다는 점을 이용한 조기 종료 최적화는 사용하지 않습니다.
- 각 행은 해당 검색이 완료된 상태를 유지하는 동안 다른 검색은 계속됩니다. 현재 후보 구간은 현재 탐색 결과를 적용하기 전에 표시됩니다.
수업에서 해 보기
- Q1비교를 한 번만 하고도 이진 검색에서 남은 위치의 절반을 제외할 수 있는 이유는 무엇인가요?
- Q2값이 32개인 배열에서 마지막 값을 찾으려면 각 방법으로 비교를 몇 번 해야 하나요?
- Q3정렬되지 않은 배열에 같은 중간점 규칙을 적용하면 무엇이 잘못되나요?
자주 묻는 질문
이진 검색은 왜 홀수인 대상 값을 찾지 못하나요?
배열의 모든 항목은 짝수입니다. 홀수인 대상 값은 일치할 수 없으므로 후보 구간은 결국 비게 되고 알고리즘은 값을 찾지 못했다고 보고합니다.
한 행은 왜 더 이상 움직이지 않나요?
해당 탐색은 이미 완료되었습니다. 단계를 진행하면 다른 알고리즘이 계속 실행되어 두 알고리즘의 총 비교 비용을 비교할 수 있습니다.