이분 탐색

백준 문제

문제 바로가기

문제 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을 출력한다.

예제 입력 1 5 4 1 5 2 3 5 1 3 7 9 5 예제 출력 1 1 1 0 0 1

TIL

• 백준의 시간제한 1초는 10^8, 즉 1억번의 연산을 할 수 있는 시간이다. 이에 맞게 알맞은 시간 복잡도를 갖는 알고리즘을 채택해라.

FeedBack

• binaraySearch는 정렬된 리스트에서만 구현할 수 있다. 처음에 주어진 리스트가 정렬되지 않음을 간과하였다.
• 지금은 MergeSort를 직접 구현 못하여 다른 사람의 코드를 가져와서 해결했다. 자료구조 복습할 때 반드시 직접 구현할 수 있게 만들자.
• C언어로 백준 풀려니까 동적 메모리부터 여러 가지로 귀찮다. 그러나 자료구조 공부 끝나면 바로 C++으로 갈아타자.

내 접근

첫 시도 : binary Search
“리스트가 정렬되지 않았구나, 정렬을 시키자.”
두 번째 시도 : Selection Sort + binary Search
“Selection Sort는 O(N^2)의 시간복잡도를 가지므로 시간 초과. O(NlogN)를 가지는 정렬 알고리즘을 채택하자”
세 번째 시도 : Merge Sort + binary Search

내 코드

//MergeSort 부분의 출처 : https://airsbigdata.tistory.com/167
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100000
int binarySearch(int* array, int size, int target);
int sorted[MAX_SIZE];
void merge(int list[], int left, int mid, int right) {
	int i, j, k, l;
	i = left;
	j = mid + 1;
	k = left;

	/* 분할 정렬된 list의 합병 */
	while (i <= mid && j <= right) {
		if (list[i] <= list[j])
			sorted[k++] = list[i++];
		else
			sorted[k++] = list[j++];
	}

	// 남아 있는 값들을 일괄 복사
	if (i > mid) {
		for (l = j; l <= right; l++)
			sorted[k++] = list[l];
	}
	// 남아 있는 값들을 일괄 복사
	else {
		for (l = i; l <= mid; l++)
			sorted[k++] = list[l];
	}

	// 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
	for (l = left; l <= right; l++) {
		list[l] = sorted[l];
	}
};
void merge_sort(int list[], int left, int right) {
	int mid;

	if (left < right) {
		mid = (left + right) / 2; // 중간 위치를 계산하여 리스트를 균등 분할 -분할(Divide)
		merge_sort(list, left, mid); // 앞쪽 부분 리스트 정렬 -정복(Conquer)
		merge_sort(list, mid + 1, right); // 뒤쪽 부분 리스트 정렬 -정복(Conquer)
		merge(list, left, mid, right); // 정렬된 2개의 부분 배열을 합병하는 과정 -결합(Combine)
	}
}

int main()
{
	//input
	int n, m;
	scanf("%d", &n);
	int* list = (int*)malloc(sizeof(int) * n);
	for (size_t i = 0; i < n; i++)
		scanf("%d", &list[i]);
	scanf("%d", &m);
	int* targets = (int*)malloc(sizeof(int) * m);
	for (size_t i = 0; i < m; i++)
		scanf("%d", &targets[i]);

	//sort
	merge_sort(list, 0, n - 1);


	//search
	for (size_t i = 0; i < m; i++)
		printf("%d\n", binarySearch(list, n, targets[i]));


	free(list);
	free(targets);
	return 0;
}



int binarySearch(int* array, int size, int target) {
	int left = 0, right = size - 1;
	int mid;
	while (right >= left) {
		mid = (left + right) / 2;
		if (target == array[mid]) return 1;
		else if (target > array[mid]) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	return 0;
}

다른 사람 코드 (in C++)

역시 C++은 내장함수인 sort() 함수가 있어 코드가 매우 짧다. 만일 내가 C++로 했다면 sort() 함수를 바로 가져다 쓸 수 있어 편했을 텐데, 그랬다면 위에 서술한 시간복잡도에 따른 알고리즘의 채택 과정을 경험하지 못한 채 문제 풀이를 끝냈을 것이다. (sort 함수는 NlogN의 quick Sort를 이용해 제작됨) 귀찮은 면이 매우 많은 low-level인 C언어이지만 그만큼 하나하나 내가 다 설정해 주어서 공부할 때는 이런 점에서 도움이 된다.

#include<bits/stdc++.h>
using namespace std;
int n,m,t;
int bs(int arr[],int p,int r,int num)
{
    if(p<=r)
    {
        int mid=(p+r)/2;
        if(arr[mid]==num)
            return 1;
        else if(arr[mid]>num)
            return bs(arr,p,mid-1,num);
        else
            return bs(arr,mid+1,r,num);
    }
    return 0;
}

int main()
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> n;
    int arr[n]={};
    for(int i=0;i<n;i++)
        cin >> arr[i];
    sort(arr,arr+n);
    cin >> m;
    for(int i=0;i<m;i++)
    {
        cin >> t;
        cout << bs(arr,0,n,t) << "\n";
    }

}