인프런 커뮤니티 질문&답변

17.15강 이진탐색 강의의 13:10부분입니다.

이진탐색에서 만약 탐색을 실패하는 경우 어째서 first >last라는 상황이 발생하는지 잘 모르겠습니다.

반복문을 반복해야할 상황이(탐색해야할 상황이) first <= last인 상황이라는 것을 알겠지만, first > last가 되는 상황은 어떻게 유도되는지 모르겠습니다.

#include <stdio.h>
int BSearch(int ar[], int len, int target) {
int first = 0;
int last = len - 1;
int mid;

while (first <= last) {
mid = (first + last) / 2;

if (target == ar[mid])
return mid;
else {
if (target < ar[mid])
last = mid - 1;
else
first = mid + 1;
} }
return -1;
}

int main(void)
{
int arr[] = { 1,3,5,6,7,9,11,13,15,19 };
int index; index = BSearch(arr, sizeof(arr) / sizeof(int), 3);
if (index == -1)
printf("해당값 없음\n");
else printf("타겟의 위치 : %d\n", index);
return 0;
}