글 읽기 - 이분 탐색 수찾기

blueskytime 6년 전 0

이분 탐색을 구현하여 풀려는데

컴파일은 되나 틀렸다고 합니다.

이분 탐색 알고리즘은 첫번째 배열의 시작 인덱스를 left로, null문자가 저장된 인덱스-1을 right로 두고 mid는 (left+right)/2로 두고 두번째 배열의 인덱스 값이 mid 값 보다 작은경우는 right를 mid-1로. 반대의 경우는 left를 mid+1로 두었습니다.

제가 생각하는 경우는

1.첫번째 배열에서 받는 배열이 0개만큼 받을 때 모두 0.

2.두번째 베열에서 값이 첫번째 받는 값의 최소보다 작은 경우와 최대보다 큰경우 0

3.두번째 배열에서 값이 정렬된 값 사이이며 그 값이 없을 때 0

또 다른 경우가 있나요?

#include<stdio.h>
#include <algorithm>
using namespace std;
int main() {
	int n, m, i;
	int left, mid, right;
	char arr1[100001];
	char arr2[100001];
	scanf("%d", &n);

	for (i = 0; i < n; i++)           //첫번째 입력
		scanf("%d", &arr1[i]);

	sort(arr1, arr1 + n);            //정렬

	scanf("%d", &m);
	for (i = 0; i < m; i++) {        //두번째 입력과 동시에 이분탐색
		scanf("%d", &arr2[i]);
		left = 0;
		right = n - 1;
		mid = (right + left) / 2;
		if (n == 0)
			printf("0\n");
		while (left <= right) {
			//printf("left:%d right:%d mid:%d \n", left, right, mid);
			if (arr2[i] == arr1[mid]) {
				printf("1\n");
				break;
			}
			else if ((left+1 == right && arr2[i] > arr1[left] && arr2[i] < arr1[right]) 
             || arr2[i]<arr1[0] || arr2[i] >arr1[n - 1] ||(arr2[i] > arr1[right] || arr2[i] < arr1[left])) {
				printf("0\n");
				break;
			}
			if (arr2[i] > arr1[mid]) {
				left = mid+1;
			}
			else if (arr2[i] < arr1[mid]) {
				right = mid-1;
			}
			mid = (left + right) / 2;
		}
	}
	return 0;
}

kyhdudgns113 6년 전 1

수의 범위는 int 정수형입니다. char 형태로 받으시면 아니되죠 ㅎㅎ

blueskytime 6년 전 0

와 진짜 감사합니다 ㅠㅠ..

int형으로 고치니 바로 맞네요 ㄷㄷ..

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

문제

문제

출처

ICPC

이분 탐색 수찾기

blueskytime 6년 전 0

kyhdudgns113 6년 전 1

blueskytime 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말