[정보처리기사 필기 요약] #2-2. 이진 탐색

1. 이진 탐색

- 가운데를 보고 절반씩 버린다

 

① 중간 위치를 찾음

② 찾는 값과 비교

③ 찾는값보다 중간값이 작으면 왼쪽 다 버림

④ 찾는값보다 중간값이 크면 오른쪽 다 버림

⑤ 반복

 

 

 

정답 : 3번

해설 : 

 

[비교횟수 : 1회차]

① 중간 위치를 찾음 (인덱스 기준)

low = 0

high = 14

mid = (0+14) / 2 = 7

 

arr[7] = 8

 

② 찾는 값과 비교

14 vs 8

 

③ 찾는값보다 중간값이 작으면 왼쪽 다 버림

-> 레코드 9 10 11 12 13 14 15

 

 

[비교횟수 : 2회차]

① 중간 위치를 찾음 (인덱스 기준)

low = 8

high = 14

mid = (8+14) / 2 = 11

 

arr[11] = 12

 

② 찾는 값과 비교

14 vs 12

 

③ 찾는값보다 중간값이 작으면 왼쪽 다 버림

-> 레코드 13 14 15

 

 

[비교횟수 : 3회차]

① 중간 위치를 찾음 (인덱스 기준)

low = 12

high = 14

mid = (12+14) / 2 = 13

 

arr[13] = 14

 

② 찾는 값과 비교

14 vs 14

=일치하니까 종료