백준(BOJ) 1920 수찾기 *

가장 기본적인 이분탐색 방법입니다...

본인의 머리속에서 떠오르는데로 짜고 다른분들의 코드를 보니
종료시점에서 찾고자 하는수를 찾지 못한 조건을
left>=right로 주는 것이 정석적인 방법인거 같다.

이하 생략~

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <queue>
#include <set>
#include <utility>
#include <functional>
#define MAX 40005
#define MOD 1000000007
#pragma warning(disable:4996)
using namespace std;

int n, m, tmp, lft, mid, rht;
int map[100005];

int finder(int dest)
{
	while (1)
	{
		if (map[mid] == dest)
			return 1;
		// 만약 찾고자하는 값을 찾은경우

		else if (map[mid] < dest)
		{
			lft = mid + 1;
			mid = (lft + rht) / 2;
		}
		// 찾지 못하였지만 찾고자 하는값이 중간값보다 작은 경우
		else
		{
			rht = mid - 1;
			mid = (lft + rht) / 2;
		} 
		// 찾지 못하였지만 찾고자 하는값이 중간값보다 큰 경우
		if (dest < map[lft] || map[rht] < dest)
			return 0;
		// 이분 탐색을 처음으로 생각하여 종료시점을 이렇게 설정하고 풀었다.
		// 다른 분들은 보통 lft>=right를 조건으로 두셨다.
	}
}

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

	scanf("%d", &m);
	sort(map, map + n);
	// 이분 탐색을 하기 위해서는 정렬이 필요로 합니다.

	for (int i = 0; i < m; i++)
	{
		lft = 0, rht = n - 1; mid = (lft + rht) / 2;
		// 초기값을 설정해준다.

		scanf("%d", &tmp);
		int ans = finder(tmp);
		// 이분탐색을 시작한다.

		if (ans)
			printf("1\n");
		else
			printf("0\n");
	}
	return 0;
}