[자료구조] 이진탐색

왜 중앙을 빼야하는가?

 

 

예를 들어 배열이 있다.

1 2 4 5 6 7 8 10

 

내가 찾는 값은 3이다.

 

3을 찾아 보겠다.

1 2 4 5 6 7 8 10

↑ F   ↑ C      ↑ L

처음 중앙 값은 5이다.

중앙을 빼지 않고 진행해 보겠다.

5는 타겟:3 보다 크기 때문에 오른쪽영역은 버린다.

 

1       2      4      5

↑ F  ↑ C           ↑ L

 

중앙값보다 3이 더 크기 때문에 왼쪽은 버린다. F를 C 값으로 바꾸고 중앙 값(C)를 다시 구한다.

 

2      4      5

↑ F  ↑ C  ↑ L

 

중앙값보다 3이 작기때문에 오른쪽은 버린다. L값을 C값으로 바꾸고 중앙 값(C를) 다시구한다. (F index + L index) / 2

 

2               4

↑ F,C        ↑ L

중앙값보다 3이 크기때문에 왼쪽은 버린다.

 

 

4

↑ F,C, L

중앙 값보다 3이 크기때문에 오른쪽(L)은 버리고 L과 중앙값을 같게한다.

 

4

↑ F,C, L

중앙 값보다 3이 크기때문에 오른쪽은 버리고 L과 중앙값을 같게한다.

 

4

↑ F,C, L

중앙 값보다 3이 크기때문에 오른쪽은 버리고 L과 중앙값을 같게한다.

.

.

.

중앙을 제외시키지 않았기 때문에 무한루프에 빠지고 말았다.

-> 중앙을 제외시키지 않는다는 것은 이미 비교연산을 한 중앙을 한번 더 연산하겠다는 의미이며

만약 배열에 찾는 값이 없다면 무한루프에 빠진다는 의미이기도 하다.

따라서 중앙값을 제외시키고 비교연산을 해야한다.