백준 #1920

(https://www.acmicpc.net/problem/1920)

수찾기

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

새로(다시한번) 안 사실들!

• 이진탐색 시간 복잡도

• 이진탐색 쓰기 전에 탐색하고자 하는 리스트 정렬 필수

• 퀵소트 qsort()

• const void *는 void형 상수를 가리키는 포인터라는 뜻이다.

  compare 함수 내에서 포인터의 값을 마음대로 바꾸면 큰일 난다.

처음생각

for 문 두번 돌리면 되는거 아냐?

음...아닌것이었음

for문 두번 돌리면 시간복잡도 O(n^2)됨
근데 N과M의 최댓값이 10^5 임-> 시간 엄청 걸림

시간줄이는게 관건

이진탐색

이진탐색 시간복잡도: O(log2n)
:시간 엄청 줄일 수 있음

*이진탐색에 대한 개념내용은 전 <자료구조 복습_탐색> 파트에 해놨음

단, 이진탐색하기전에 리스트 정렬 필수임.

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

int compare(const void *a, const void *b)
{
	return *(int*)a > *(int*)b ? 1 : (*(int*)a < *(int*)b ? -1 : 0);
}

int binary_search(int arr[], int num, int size)
{
	int front, rear, pivot;
	front = 0;
	rear = size - 1;
	while (1) {
    	pivot = (front + rear) / 2;
    	if (arr[pivot] == num) return 1;
    	if (arr[front] == num) return 1;
    	if (arr[rear] == num) return 1;

    	if (arr[pivot] < num)
       	 	front = pivot + 1;
    	else 
        	rear = pivot - 1;
   		 if (front >= rear)
        return 0;
       }
}

int main(void){
	int n;
	scanf("%d", &n);
	int *arr = (int*)malloc(n * sizeof(int));

	for(int i = 0; i < n; i++){
    	scanf("%d", &arr[i]);
	}

	int m;
	scanf("%d", &m);
	int *arr2 = (int*)malloc(m * sizeof(int));

	for(int i = 0; i < m; i++){
    	scanf("%d", &arr2[i]);
}

	qsort(arr, n, sizeof(int), compare);

	for(int j = 0; j < m; j++){
    	printf("%d\n", binary_search(arr, arr2[j], n));
	}
		return 0;
}