[binary search] 1920번, 수 찾기

binary search 문제 중 가장 simple한 문제이지 않을까 싶다. 

혹시 binary search에 대해서 잘 모른다면 아래 글을 읽어주시길 바란다.

 

https://77monkey.tistory.com/15

[알고리즘] binary search, 이진탐색

 

오늘은 문제는 아래와 같다.

문제를 확인했으면 이제 문제를 풀어보자.

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

1920번: 수 찾기

 

1. 문제 파악

문제에서 사실 다 알려주고 있어서 어려울 것이 없다.

단지 주의할 것이 있다. 

binary search를 사용하려면 오름차순 정렬을 해야 한다. 

오름차순 정렬이 된 상태에서 X라는 정수가 있는지 찾아야 한다. 

입력 마지막 줄에 정수의 범위가 나오는데, int로 처리 가능하다는 것을 나타내기 위해서이다. 

 

코드에서 binary search를 하면서 헷갈릴만한 부분이 배열의 index 부분일 것이다.

배열에 들어있는 값이 무엇인지는 우리는 모른다.

특히 정렬되어 input이 들어오지 않기 때문에 정렬이 되면 그 값이 음수일지, 양수일지 전혀 감이 안 잡힌다. 

하지만 확실히 알 수 있는 값이 있으니, 그게 바로 배열의 index이다.

그렇기 때문에 start, end, mid 값을 배열의 index로 잡고,

찾고자 하는 값과 비교할 때만 배열의 mid 값(arr[mid])을 확인한다.

현재 백준 예제는 1, 2, 3, 4, 5로 들어와서 배열의 index와 헷갈릴 수 있다.

 

input을 아래와 같이 주었다고 생각하면 조금 이해하기 쉬울 수 있다.

5
100 500 0 200 -100
3
200 300 0

내가 작성한 코드는 [0, N-1] 이지만, 개인에 따라서 [1, N]으로 작성해도 된다.

아래 예시는 [0, N-1]일 때를 가정하고 작성했다. 

참고로,, 대괄호는 포함이고, 소괄호는 미포함을 의미한다.

따라서 ' [ '는 이상, ' ] '는 이하, ' ( '는 초과, ' ) '는 미만을 뜻한다.

output은 아래와 같다.

1
0
1

 

참고로 정렬은 merge sort를 사용하였다.

 

2. 제출 코드

 

 

#include <stdio.h>

#define MAXN (100000+10)

int arr[MAXN];
int atemp[MAXN];

int N;
int M;

// merge sort
void sort(int s, int e)
{
	int m = (s + e) / 2;
	int i = s, j = m + 1, k = s;

	if (s >= e) return;
	sort(s, m); sort(m + 1, e);

	while (i <= m && j <= e)
	{
		if (arr[i] < arr[j])
		{
			atemp[k++] = arr[i++];
		}
		else atemp[k++] = arr[j++];
	}

	while (i <= m)	atemp[k++] = arr[i++];
	while (j <= e)	atemp[k++] = arr[j++];

	for (i = s; i <= e; i++)
	{
		arr[i] = atemp[i];
	}
}

int search(int val)
{
	int s = 0;
	int e = N - 1;
	int m;

	while (s <= e)
	{
		m = (s + e) / 2;

		if (arr[m] == val)	return 1;
		else if (arr[m] < val)	s = m + 1;
		else e = m - 1;
	}

	return 0;
}

int main(void)
{
	register int i;
	int find;

	scanf("%d", &N);

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

	sort(0, N - 1);

	scanf("%d", &M);

	for (i = 0; i < M; i++)
	{
		scanf("%d", &find);
		printf("%d\n", search(find));
	}

	return 0;
}