왜 중앙을 빼야하는가?
예를 들어 배열이 있다.
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과 중앙값을 같게한다.
.
.
.
중앙을 제외시키지 않았기 때문에 무한루프에 빠지고 말았다.
-> 중앙을 제외시키지 않는다는 것은 이미 비교연산을 한 중앙을 한번 더 연산하겠다는 의미이며
만약 배열에 찾는 값이 없다면 무한루프에 빠진다는 의미이기도 하다.
따라서 중앙값을 제외시키고 비교연산을 해야한다.