[1920] 수 찾기

#define _CRT_SECURE_NO_WARNINGS
 
#include <stdio.h>
 
#include <stdlib.h>
 
 
 
void quickSort(int *data, int start, int end) {
 
    if (start >= end) { //원소가 1개인 경우
 
        return; //바로 return 
 
 
 
    }
 
    int key = start; //키(피벗값잡기)는 첫번째 원소
 
    int i = start + 1; //왼쪽부터 하나씩 큰값을 찾을 때의 인덱스 
 
    int j = end; // i는 왼쪽 출발 지점, j는 오른쪽 출발 지점
 
    int temp; //임시 변수
 
 
 
    while (i <= j) { //엇갈릴 때까지 반복
 
        while (data[i] <= data[key] && i <= end) {//i가 키값보다 큰 값을 만날 때까지 
 
            i++; //오른쪽으로 이동 
 
        }
 
        while (data[j] >= data[key] && j > start) {//키 값보다 작은 값을 만날때까지, j>start로 제한을 걸어둬야 설령 j값이 항상 key(피벗)값보다 커도배열을 벗어나지 않는다. 
 
            j--; //j를 오른쪽으로 이동 
 
        }
 
        if (i > j) {//현재 엇갈린 상태이면 키값과 교체 
 
            temp = data[j];
 
            data[j] = data[key];
 
            data[key] = temp;
 
        }
 
        else {//엇갈리지 않았다면 j값과 i값 교체 
 
            temp = data[j];
 
            data[j] = data[i];
 
            data[i] = temp;
 
        }
 
 
 
    }
 
 
 
    quickSort(data, start, j - 1);//이전 피벗값의 왼쪽에서 정렬수행 
 
    quickSort(data, j + 1, end); //이전 피벗값의 오른쪽에서 정렬수행 
 
}
 
 
 
 
 
int main() {
 
    int n_size, m_size, left = 0, right, mid, temp;
 
    int n_numPtr[100000] = { 0, };
 
    int m_numPtr[100000] = { 0, };
 
    scanf("%d", &n_size); //탐색하는 배열의 사이즈 입력
 
    for (int i = 0; i < n_size; i++) //탐색하는 배열에 요소 입력
 
        scanf("%d", &n_numPtr[i]);
 
    quickSort(n_numPtr, 0, n_size - 1);
 
    /*for (int i = 0; i < n_size; i++)//탐색하는 배열 정렬

    {

        for (int j = 0; j < n_size-1; j++) {

 

            if (n_numPtr[j] > n_numPtr[j+1]) {

                temp = n_numPtr[j];

                n_numPtr[j] = n_numPtr[j+1];

                n_numPtr[j+1] = temp;

            }

        }

    }    */
 
    scanf("%d", &m_size);//찾고자 하는 배열 사이즈 입력
 
 
 
    for(int i=0;i<m_size;i++)
 
        scanf("%d", &m_numPtr[i]);
 
 
 
    for (int i = 0; i < m_size; i++) { 
 
        left = 0;
 
        right = n_size - 1;
 
        
 
        while (left <= right) { //바로 이분탐색 시작;
 
            mid = (left + right) / 2;
 
            if (n_numPtr[mid] > m_numPtr[i]) //탐색배열의 가운데 요소가 찾고자 하는 값보다 크다면
 
                right = mid - 1; //오른쪽 인덱스를 가운데 인덱스 -1
 
            else if (n_numPtr[mid] < m_numPtr[i]) //탐색 배열의 가운데 요소가 작다면
 
                left = mid + 1; //왼쪽 인덱스를 가운데 인덱스 +1
 
            else //탐색배열의 가운데값과 찾고자 하는 값이 같다면 종료
 
                break;
 
        }
 
 
 
        if (n_numPtr[mid] == m_numPtr[i])
 
            printf("1\n");
 
 
 
        else
 
            printf("0\n");
 
    }
 
}