어떤 문제인가?

정렬 및 이진탐색을 사용해서 주어진 수가 주어진 배열 내에 있는지 확인하는 문제.

함수가 있었네??

C에서는 qsort, bsearch 함수를 제공한다. 아니 그게 있었으면 진작에 이야기좀 해주지..

#include <stdio.h>
#include <stdlib.h>

int p(int* a, int l, int h) {
    int pv = a[h],j=l,i=l-1,t;
    for(;j<h;j++) {
        if(a[j]<pv) {
            t=a[++i];
            a[i]=a[j];
            a[j]=t;
        }
    }
    t=a[i+1];
    a[i+1]=a[h];
    a[h]=t;
    return i+1;
}

void q(int* a, int l, int h) {
    int pi=0;
    if(l<h) {
        pi=p(a,l,h);
        q(a,l,pi-1);
        q(a,pi+1,h);
    }
}
    
int main() {
    int i=0,l=0,m=0,t=0,N,M,*A,k;
    scanf("%d",&N);
    A=(int*)calloc(sizeof(int),N);
    for(;i<N;i++) scanf("%d",&A[i]);
    q(A, 0, N-1);
    scanf("%d",&M);
    for(i=0;i<M;i++) {
        scanf("%d",&k);
        l=0;m=N-1;
        while(1) {
            t=(l+m)/2;
            if(k==A[t]) {
                printf("1\n");
                break;
            }
            if(l>=m) {
                printf("0\n");
                break;
            }
            if(k<A[t]) m=t-1;
            else if(k>A[t]) l=t+1;
        }
    }
}

난 그런줄도 모르고 밑바닥에서부터 구현했잖아..

함수 둘러보기

• qsort : https://docs.microsoft.com/ko-kr/cpp/c-runtime-library/reference/qsort?view=msvc-160
• bsearch : https://docs.microsoft.com/ko-kr/cpp/c-runtime-library/reference/bsearch?view=msvc-160

남들은 어떻게 풀었나

당연히 위에 있는 함수를 썼죠..

#include <stdio.h>
#include <stdlib.h>
int A[100001] = {0,};
int compare(const void *first, const void *second)
{
	if (*(int*)first > *(int*)second)
		return 1;
	else if (*(int*)first < *(int*)second)
		return -1;
	else
		return 0;
}
int main() 
{
	int n, i, b, m;
	scanf("%d",&n);
	for ( i=0; i<n; i++ ) {
		scanf("%d",&A[i]);		
	}
	qsort(A, n, sizeof(int), compare);
	scanf("%d",&m);
	for ( i=0; i<m; i++ ) {
		scanf("%d",&b);
		if ( (int*)bsearch(&b, A, n, sizeof(int), compare) )
			printf("1\n");
		else
			printf("0\n");		
	}
	return 0;
}

rmsxo1321님의 코드
-> https://www.acmicpc.net/source/2859402

밑바닥에서 쌓아올리는데 참고한 곳들

1. https://www.google.com/amp/s/www.geeksforgeeks.org/quick-sort/amp/
2. https://www.google.com/amp/s/www.geeksforgeeks.org/binary-search/amp/