이분 탐색은 다음과 같은 구조로 되어있다.
1. left = 처음 값
2. right = 마지막 값
3. 반복문의 시작
if (left 와 right가 차이가 없으면) break
mid = (left + right) / 2
if 용의 선상이 mid 아래면 right = mid
if 용의 선상이 mid 위면 left = mid
여기서 생각해야 될 것은 두개 뿐이라는 것을 알 수 있다.
1. 이분 탐색은 선형 자료구조에서 '하나'의 값을 선택하기 위한 알고리즘이라는 것을 염두에 두면
'left 와 right가 차이가 없으면' => 이부분은 left + 1 == right 이때 while문이 멈추도록 코딩해야 한다는 것이다.
즉 while문의 조건은 항상 while(left + 1 < right) 이여야 한다는 것이다.
이것은 left와 right가 값이 아닌 값과 값사이의 경계를 나타내기 때문이다.
예를 들어 [1, 4, 5, 7, 9, 11] 이라는 배열에서 8이상인 첫번째 값의 인덱스를 찾는 문제를 상정해 보자. 즉 answer = 4다
이때 left = 4, right = 5가 되도록하여 (여기서 격벽의 위치는 arr[idx]의 왼쪽에 있는 격벽이 idx의 위치를 갖는다하자)
1 4 5 7 { 9 } 11 같은 식으로 left와 right는 정답을 감싸는 격벽으로 생각해야 된다는 것이다. 이를위해 고려하는 것은 2번 고려사항이다.
2. 다음 right와 left를 결정하는 두개의 if문의 구조는 두가지 가능성이 있다는 것이다.
if (arr[mid] <= 8) left = mid
if (arr[mid] > 8) right = midif (arr[mid] < 8) left = mid
if (arr[mid] >= 8) right = mid이 둘중 하나는 틀렸다. 무엇이 틀렸을까
이 문제는 8을 살펴 보면 된다. if문은 두개지만 총 3개라고 생각해도 되기 때문이다. 바로
if (arr[mid] < 8) left = mid
if (arr[mid] == 8) ????
if (arr[mid] > 8) right = mid에서 물음표에 들어갈 코드를 적는 문제로 봐도 된다는 의미다.
그럼 물어보자 8은 답인가? 그렇다 왜냐하면 문제는 8이상이 되는 arr의 원소의 index를 구하여라 였기 때문이다.
{ 답 }에 이르기 전단계로 세 가지를 상정해 보자 { ㅇ | 답 }, { 답 | ㅇ }, { 답 | ㅇ ㅇ }
이 세가지 말고는 { 답 } 의 이전단계로 상정 할 수 없다.
이 중 arr[mid]가 "답"인 경우는 하나 뿐이다 { ㅇ | 답 } 이 경우 뿐이다.
만약 "답"이 8이라면 가운데 if 문에 들어가게 되고 따라서 ???일 때를 경정할 수 있다.
즉 { ㅇ | 8 }일때 left = mid가 되어야 { 8 }이 되므로 ???에 들어갈 말은 left = mid이고 따라서
전자
if (arr[mid] <= 8) left = mid
if (arr[mid] > 8) right = mid이것이 답임을 알 수 있다.
즉 여기서 결론을 내리자면 { 답 }에 이르는 경우의 수를 구한 다음 arr[mid]가 답이 되는 경우의 수를 골라 이때 기준이 되는 숫자를 넣어서 left를 움직여야 될지 right를 움직여야 할지를 결정하면 된다는 것이다.