다음 탐색 알고리즘을 이용하여 아래 리스트에서 키(key) 34를 찾을… | [7급 국가직 자료구조론] 24년 1회차 기출문제 상세 페이지

다음 탐색 알고리즘을 이용하여 아래 리스트에서 키(key) 34를 찾을 경우, 필요한 반복 연산 횟수는? (단, low 변수에는 0, high 변수에는 15가 전달된다)
int a_search(int list[], int key, int low, int high) {
    int middle;
    while(low<=high) {
        middle=(low+high)/2;
        if(key==list[middle])
            return middle;
        else if(key>list[middle])
            low=middle+1;
        else
            high=middle-1;
    }
    return -1;
}

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
6
11
13
18
20
22
27
29
30
34
38
41
42
45
47

3

4

5

6

키 34는 반복 4회 만에 찾는다.
코드는 정렬된 리스트에 대한 이진 탐색이며, 반복마다 middle 값과 비교해 범위를 절반으로 줄인다.
1회: low=0, high=15 → middle=7, list[7]=27 < 34이므로 low=8
2회: low=8, high=15 → middle=11, list[11]=38 > 34이므로 high=10
3회: low=8, high=10 → middle=9, list[9]=30 < 34이므로 low=10
4회: low=10, high=10 → middle=10, list[10]=34로 탐색 성공
3회째 비교 대상은 30이어서 아직 키를 찾지 못한 상태다.
5회는 4회째에 return으로 반복이 끝나므로 나올 수 없다.
6회는 원소 16개에 대한 이진 탐색의 최대 반복 수인 5회보다도 많다.