[코드트리 챌린지] 2주차

---

실력진단 결과

코드트리 2주차 실력진단 결과

 

---

오늘의 학습

이진탐색 & 이분탐색

업/다운 게임이라는 것을 들어보셨나요? 한 사람이 수를 생각하고, 다른 사람이 수를 예측해서 부르면 그것보다 큰지, 작은지 불러주면서 최대한 빨리 그 수를 맞추는 게임입니다. 많은 사람들이 수를 처음 예측할 땐 범위의 가운데에 해당하는 숫자를 부르고, 그 이후엔 업/다운에 맞춰 특정 구간의 가운데를 부르는 방법으로 수를 추측합니다.
이진탐색의 아이디어도 저것과 동일합니다. 찾아야 하는 수의 범위 중 가운데의 값과 찾고자 하는 값을 비교하여 대소관계에 따라 특정 구간으로 이동하는 것을 반복하는 것입니다.

업/다운 게임에서 비춰보면, '다운'이라는 말을 들으면 우리는 그 값보다 더 작은 값을 선택해야 하고, '업'을 외쳤다면 더 큰 값을 선택해야 합니다. 이진탐색에서도 저러한 과정을 수행하기 위해선, 당연하게도 대소관계에 따라 실제 찾는 값도 작거나 커져야 하기 때문에 배열에 들어있는 값은 반드시 정렬이 되어 있어야 합니다.

 

당연히 우리가 찾는 범위 속 원소의 갯수가 1개로 줄어들 때 까지 계속 탐색을 진행해야 하기 때문에 while문을 통해 조건을 걸고, 이후 중간에 위치한 값의 대소관계에 따라 left와 right의 값을 계속 바꿔가면서 진행하는 것을 볼 수 있습니다. 단, while 조건을 걸 때 left <= right 이렇게 등호를 꼭 넣어야 단 하나의 숫자만 남았을 경우에도 올바르게 찾아집니다. 계속 탐색을 반복하며, 그 중 가운데 위치에 해당하는 값인 arr[mid]와 찾으려고 하는 숫자인 target이 일치하면, 해당 위치인 mid를 반환해주게 됩니다. while문이 끝났는데도 불구하고 아직 return이 되지 않았다면, -1을 반환해 원하는 값이 없다는 표시를 해주게 됩니다. 또, mid = (left + right) / 2 에서 left + right 값이 홀수라면, mid는 2로 나눈 뒤 버림한 위치에 가게됨에 유의합니다.

왜 left는 mid + 1이고, right는 mid - 1일까요? arr[mid]값이 target값이 아니었으니 mid는 target을 포함할 숫자 범위에서 명확히 제외됩니다. 따라서 mid 위치를 제외한 범위로 left, right를 움직여줘야 함에 유의합니다.

이진탐색 & 이분탐색 코드

int left = 0;
int right = N - 1;
while (left <= right) {
    int mid = (left + right) / 2;
    if(arr[mid] == target) {
        idx = mid;
        break;
    }
    if(arr[mid] > target) {
    	right = mid - 1;  
    } else {
       left = mid + 1;
    }
}