[BOJ]1920번 수찾기

문제

수찾기

코드

#include <iostream>

using namespace std;

int ft_search(int *arr, int n, int x)
{
	int start = 0;
	int end = n - 1;
	int mid = (start + end)/2;

	while (start <= end)
	{
		int mid = (start + end)/2;
		if (x == arr[mid] || x == arr[start] || x == arr[end])
			return (1);
		else if (x < arr[mid] && x > arr[start])
			end = mid - 1;
		else if (x > arr[mid] && x < arr[end])
			start = mid + 1;
		else
			return (0);
	}
	return (0);
}

void ft_merge(int *arr, int *temp, int st, int ed)
{
	int mid = (st + ed) / 2;
	int i = st;
	int j = st;
	int k = mid + 1;

	while (i <= mid && k <= ed)
	{
		if (arr[i] > arr[k])
		{
			temp[j] = arr[k];
			j++;
			k++;
		}
		else
		{
			temp[j] = arr[i];
			j++;
			i++;
		}
	}
	if (i > mid)
	{
		while (k <= ed)
		{
			temp[j] = arr[k];
			j++;
			k++;
		}
	}
	else
	{
		while (i <= mid)
		{
			temp[j] = arr[i];
			j++;
			i++;
		}
	}
	for (int i = st; i <= ed; i++)
		arr[i] = temp[i];
}

void ft_sort(int *arr, int *temp, int st, int ed)
{
	if (st < ed)
	{
		int mid = (st + ed) / 2;
		ft_sort(arr, temp, st, mid);
		ft_sort(arr, temp, mid + 1, ed);
		ft_merge(arr, temp, st, ed);
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m;

	cin >> n;

	int arr[n];
	int temp[n];

	for (int i = 0; i < n; i++)
		cin >> arr[i];
	
	ft_sort(arr, temp, 0, n - 1);

	cin >> m;

	int arr2[m];

	for (int i = 0; i < m; i++)
	{
		cin >> arr2[i];
		cout << ft_search(arr, n, arr2[i]) << '\n';
	}
	return (0);
}

공부할 겸 stl과 algorithm 내장 sort함수를 사용하지 않고 병합정렬로 해당 문제를 풀어봤습니다.