글 읽기 - 런타임 오류가 뜨는데 해결방법을 모르겠습니다.

wjddms0114 4년 전 0

1920번 문제가 이분탐색 문제라고 하여,

직접 binary search 함수를 만들어서 코드를 짜봤는데 계속 런타임 오류가 발생합니다.

binary search 함수는 원하는 수를 못 찾으면 범위를 반씩 줄여서 진행하니까(logn)일 것 같은데, 아닐까요?

cin.tie(0)도 해서 cin 함수 때문에 발생하는 런타임 오류는 아닌 것 같은데,

어느 부분에서 시간을 더 단축시켜야할지, 어떻게 단축시켜야할지 전혀 감이 오지 않습니다.

조언 부탁드립니다.

#include <iostream>
#include <algorithm>
using namespace std;

int verify(int *arr, int start, int end, int k) {
	int mid = (start + end) / 2;
	if (arr[mid] == k) { return 1; }
	if (start > end) { return 0; }
	if (arr[mid] < k) {
		verify(arr, mid + 1, end, k);
	}
	else if (arr[mid] > k) {
		verify(arr, start, mid - 1, k);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0); 
	int N;
	cin >> N;
	int *arr = new int[N];
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		arr[i] = a;
	}
	sort(arr, arr + N);
	int M;
	cin >> M;
	for (int j = 0; j < M; j++) {
		int la;
		cin >> la;
		cout << verify(arr, 0, N, la) << endl;
	}
	return 0;
}