[백준 10815] 이분 탐색법(binary search)

숫자 카드: 백준 10815번 문제

n개의 카드를 받았을 때,
m개의 숫자카드 중 가지고있는 카드가 무엇무엇인지를 판단하는 문제

문제 이해 및 풀이

arr1에 n개의 숫자를 받고,
std::sort 알고리즘으로 미리 정렬해놓는다.

sort 알고리즘은 <algorithm> 헤더파일에 있고
퀵소트로 정렬하여 O(nlogn)의 시간복잡도를 가진다.
sort(start, end, compare)으로
첫번째인자는 시작주소,
두번째인자는 끝주소,
마지막인자는 비교함수를 옵션으로 넣어줄 수 있다.
기본값은 오름차순 정렬이다.

다시 돌아와서,
m개의 숫자를 받아
각 숫자가 n개의 카드에 존재하는지 여부를 출력해주기 위해
바이너리서치 함수로 전달한다.
함수로 배열을 전달할 때 길이정보가 같이 넘어가지는 않으므로, 꼭 인자로 따로 넘겨주어야 한다.

재귀적 방법과 반복문을 사용하는 방법 두 가지가 있다.

재귀적 방법

처음 인덱스 0부터 끝까지 인자로 넘겨놓고,
매번 중간값을 확인한 후
더 클경우 중간값+1을 first값으로 재귀호출한다.
더 작을경우 중간값-1을 last값으로 재귀호출한다.
찾지 못했는데 first값이 last값을 초과해버리면 원하는 값이 없는것.

직관적 이해:
search(first=1, first=2) 호출의 경우
인덱스 1 2에서 중간값은 1이되고 없을경우 중간값1+1=2가 초기값 first가 된다.
즉 search(first=2, last=2)가 된다.
이번호출에서는 중간값이 2가되고 fisrt=3 last=2가 되어 탈출조건을 만족한다.

void search(int* arr1, int a, int first, int last) {
    if(first>last) {
        printf("0");
        return;
    }
    int mid = (first + last) / 2;
    if(arr1[mid] == a) {
        printf("1");
        return;
    }
    else if(arr1[mid] < a)
        search(arr1, a, mid+1, last);
    else if(a < arr1[mid])
        search(arr1, a, first, mid-1);
}

// 함수 호출부
search(arr1, arr2[i], 0, len-1);

반복문 사용 방법

함수 호출에는 배열, 찾고자하는 값, 배열길이를 인자로 넘겨준다.
while문에서 마찬가지로 first가 last를 초과하는 순간을 탈출조건으로 잡는다.

void search(int* arr1, int a, int len) {
    int first = 0;
    int last = len-1;
    int mid;

    while(first<=last) {
        mid = (first+last)/2;
        if(arr1[mid]==a) {
            printf("1");
            return;
        }
        else if(arr1[mid]<a) {
            first = mid+1;
        }
        else {
            last = mid-1;
        }
    }
    printf("0");
    return;
}