(8)실습6주차_이진탐색+순차자료_[문제3](작성중)

※문제 PDF는 다음 링크에 들어가면 다운받을 수 있다.

https://kojammin.tistory.com/95

(6)실습6주차_이진탐색+순차자료_[문제1]

 

#문제 핵심 힌트 :

힌트1 _ 위의 힌트를 봤을 때, 'N'을 입력 시, mid의 범위를 포함하고, 'Y'를 입력시 mid의 범위를 포함하지 않는다.

• 일반적인 이분 탐색 범위 나눌 때, 

A[mid] 와 Key와 비교 후, => Start - mid -1 (왼쪽 구간)|| mid + 1 - End(오른쪽구간)

즉,  mid를 포함하지 않고, 왼쪽 오른쪽 구간을 나눈다.

•  이 문제의 이분탐색 범위 나눌 때,

A[mid] 와 Key와 비교 후, => Start - mid (왼쪽 구간, 'N'입력 시)|| mid + 1 - End(오른쪽구간,'Y'입력 시)

즉, mid를 N일 때, 포함한다. (이유 :위의 사진의 문제 힌트 때문)

힌트2 _ 마지막 반환 값을 End(끝 범위)||Start(시작 범위) 값으로 한다.

##입력2 직접 해본 노트 :

 

##코드 :

 

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
 
void BinarySearch(int start, int end, int cnt) {
    if (cnt == 0) {
        // 종료 조건: cnt가 0이 되면 탐색이 끝났으므로 결과 출력
        printf("%d\n", end);
        return;
    }
 
    int mid = (start + end) / 2;
    char tmp;
 
    // 한 문자 입력 ('Y' 또는 'N')
    scanf(" %c", &tmp);
 
    // 입력에 따라 범위를 나누어 재귀 호출
    if (tmp == 'Y') {
        BinarySearch(mid + 1, end, cnt - 1);  // 'Y'면 오른쪽 범위 탐색
    }
    else {
        BinarySearch(start, mid, cnt - 1);  // 'N'면 왼쪽 범위 탐색
    }
}
 
int main() {
    int start, end, cnt;
    scanf("%d %d %d", &start, &end, &cnt);
 
    // 이진 탐색 재귀 호출
    BinarySearch(start, end, cnt);
 
    return 0;
}