1920번 - 이분 탐색 - 수 찾기

[ 풀이 ]

정수의 범위가 너무 커서 배열을 통해서 이전에 찾은 값을 저장해 두는 것은 안 될 것 같았다.
대신 탐색 경우를 조금이라도 줄이기 위해서 2가지를 조건문으로 확인했다.

1. 찾고자 하는 값이 저장된 정수 범위 내에 있는가.
2. 정수 범위의 최솟값 또는 최댓값과 동일한가.

찾고자 하는 값이 저장된 정수 범위 내에 있는 경우 이분 탐색을 진행한다.
값이 존재하면 1을 출력하고, 존재하지 않으면 bool 변수를 통해 판별하여 0을 출력하도록 했다.
(이분탐색을 별도의 함수로 정의해서 반환값으로 판별해도 좋을 것 같다.)

[ 어려웠던 점 ]

출력 초과 오류가 발생해서 이를 해결하는 데 시간이 조금 걸렸다.
탐색이 되지 않았을 때를 고려하지 않아서 발생한 문제였다.
isExist 변수로 이를 처리하니 오류를 해결할 수 있었다.

[ 코드 ]

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

using namespace std;

int n = 100000;
int m = 100000;

int main(void) {

	scanf("%d", &n);

	vector<int> nums(n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &nums[i]);
	}

	sort(nums.begin(), nums.end());

	int minNum = nums.front();
	int maxNum = nums.back();

	scanf("%d", &m);

	int target = 0;
	for (int i = 0; i < m; i++) {
		scanf("%d", &target);
        //범위 내에 있는 값인 경우
		if (target >= minNum && target < maxNum) {
			int left = 0;
			int right = nums.size() - 1;
			bool isExist = false;
			while (left <= right) {
				int mid = (left + right) / 2;
				if (nums[mid] == target) {
					printf("1\n");
					isExist = true;
					break;
				}
				else if (nums[mid] < target) {
					left = mid + 1;
				}
				else {
					right = mid - 1;
				}
			}

			if (!isExist) { //일치하는 값이 없는 경우
				printf("0\n");
			}
		}
		
		else { //최소값 또는 최댓값과 동일한 경우
			if (target == minNum || target == maxNum) {
				printf("1\n");
			}
			else {
				printf("0\n");
			}
		}
	}

	return 0;
}