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

[문제2]의 PDF는 아래의 링크에 들어가면 된다.

https://kojammin.tistory.com/95

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

[문제2]

##핵심 개념 :

[문제1]과의 차이점 :

• 제일 큰 Key값을 이진 탐색 => result값이 변하지 않음 => -1로 출력x, N으로 출력(문제 조건이 다름)
• 제일 큰 Key값/제일 작은 Key값 탐색 의 비교 :

1. 두 탐색 둘다 START == END 순간은 온다
2. 차이점 :

• 제일 큰 Key값 이진 탐색 : Result값이 업데이트 X
• 제일 작은 Key값 이진 탐색 : Result값이 계속 업데이트 O

 

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

##코드 :

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
 
int* A = NULL;
 
int result = -1;
 
void BinarySearch(int* A, int start, int end,int Key) 
{
    int n = end + 1;
 
    while (1) {
 
        int mid = (start + end) / 2;
 
        if (A[mid] == Key) 
        {
            result = mid;
            return;
        }
        else if (A[mid] < Key) 
        {
            start = mid + 1;
        }
        else 
        {
            end = mid - 1;
            result = mid;
        }
 
        if (start > end) {
            //제일 작은 Key && 제일 큰 Key 둘다 start == end 순간은 온다.
 
            //차이점 : 
            //제인 큰 key일 떄, result가 업데이트 x
            if(result==-1) result = n;
 
            //제일 작은 Key일 때, 범위가 줄면서, result 업데이트 o
            return;
        }
    }
}
 
int main() 
{
    int N,Key;
 
    scanf("%d %d", &N,&Key);
 
    A = (int*)malloc(sizeof(int) * N);
 
    for (int i = 0; i < N; i++) scanf("%d", &A[i]);
 
    BinarySearch(A, 0, N - 1, Key);
 
    printf(" %d", result);
 
    return 0;
}