[정처기 2과목] 이진 탐색(이분 탐색)

[1 ~ 15] 의 값 중에서 14를 찾을 때 비교되는 횟수는?

1-1. 최소값(min)과 최대값(max)값의 중간값(mid)을 구합니다.

        min과 max를 더한 후 2로 나눕니다. 소수점이 있을 경우 버립니다.

        (1+15)/2 = 8

1-2. mid인 8과 14를 비교합니다. 8이 더 작으므로 min을 8을 제외한 다음 수인 9로 설정합니다.

2-1. min값과 max값의 mid을 구합니다.
        (9+15)/2 = 12

2-2. mid인 12와 14를 비교합니다. 12가 더 작으므로 min을 12 다음 수인 13으로 설정합니다.

3-1. mid를 구합니다.

        (13+15)/2 = 14
3-2. mid인 14가 14와 일치합니다.

        3번만에 14를 찾았습니다.

 

이진탐색의 경우 숫자의 순서가 일정해야하고 만약 숫자가 1씩 커지는 경우가 아니면 인덱스 번호를 붙여서 계산할 수 있습니다.

방금의 경우라면 0~14 로 계산해도 결과는 동일하며, 저는 이과가 아니여서 헷갈릴까봐 실제 값으로 계산하였습니다.

 

만약 방금 경우에서 인덱스 번호로 1을 찾아보겠습니다.

 

1-1. min=0, max=14, mid=7

1-2. [7]번째 값인 8 > 1

        max를 7로 변경

2-1. min=0, max=7, mid=3 (3.5소수점버림)

2-2. [3]번째 값인 4 >1

        max를 2로 변경

3-1. min=0, max=2, mid=1

3-2. [1]번째 값인 2는 1보다 큼

        max를 1로 변경

4-1.  min=0, max=1, mid=0 (0.5소수점버림)

4-2. [0]번째 값인 1 = 1

        4번만에 찾음