글 읽기 - C 이분 탐색 이렇게 구현하면 틀린걸까요 .. ?

kl45678 2년 전 1

이분 탐색 제 생각대로 구현 후 제출 하니 틀렸다 나와서 구글링 해보니 대부분 C++ Upper Bound , Lower Bound 사용하셨던데 이 방법으로는 안될까요 ? 알려주시면 대단히 감사하겠습니다 고수분들 ㅠ

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

int T;
int answer[500001];
int key[500001];
int keycheck[500001];

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

void binary_search_tree(int arr[], int keyValue, int size, int index, int f, int r)
{
	int front, rear, pivot;
	front = f;
	rear = r;

	while (1)
	{
		pivot = (front + rear) / 2;
		if (arr[pivot] == keyValue)
		{
			keycheck[index]++;
			binary_search_tree(answer, key[index], size, index, 0, pivot - 1);
			binary_search_tree(answer, key[index], size, index, pivot + 1, T - 1);
			break;
		}
		if (arr[front] == keyValue)
		{
			keycheck[index]++;
			binary_search_tree(answer, key[index], size, index, front + 1, T - 1);
			break;
		}
		if (arr[rear] == keyValue)
		{
			keycheck[index]++;
			binary_search_tree(answer, key[index], size, index, 0, rear - 1);
			break;
		}

		if (arr[pivot] < keyValue)
			front = pivot + 1;
		else
			rear = pivot - 1;

		if (front >= rear)
			break;
	}
}

int main(void)
{
	scanf("%d", &T);
	for (int i = 0; i < T; i++)
		scanf("%d", &answer[i]);

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

	qsort(answer, T, sizeof(int), cmp);

	for (int i = 0; i < M; i++)
		binary_search_tree(answer, key[i], T, i, 0, T - 1);

	for (int i = 0; i < M; i++)
		printf("%d ", keycheck[i]);

	return 0;
}

zenith82114 2년 전 1

아래와 같이 구간이 더 좁아질 수 없는 경우에 무한 루프에 빠집니다.

kl45678 2년 전 0

감사합니다 !

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C 이분 탐색 이렇게 구현하면 틀린걸까요 .. ?

kl45678 2년 전 1

zenith82114 2년 전 1

kl45678 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말