https://www.acmicpc.net/problem/1920
문제
> N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내라.
> 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다.
> 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다.
> 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.접근
이분 탐색을 사용하는 문제이기 때문에 주어진 A 수열에서 이분 탐색을 이용해 M으로 주어진 수들을 각각 탐색해 결과를 출력한다.
문제해결
> 이분 탐색을 함수로 정의해준다. 처음엔 시작값이 인덱스 0, 끝값이 마지막인덱스(size() -1)이다.
> 탐색을 하는데 찾는 값이 없으면 left나 right가 역설되는 부분이 생긴다. 이때 까지 while문을 돌려준다.
> 비교하려는 중간값을 설정한다. 입력으로 들어온 값과 중간값을 비교해 같으면 1을 return하고 종료, 더 크면 left의 값을 중간값은 이미 비교해 같지 않다고 나왔기 때문에 중간값 +1 로 갱신한다. 더 작다면 반대로 중간값 -1 을 right로 갱신한다.
> 갱신된 left나 right값으로 중간값을 다시 설정해 또 비교한다. 최종적으로 범위가 역전되면 while문을 깨고 0을 return 한다.
> 탐색 대상 A수열을 입력받고 이분 탐색을 위해 오름차순으로 정렬한다. 찾고자 하는 M수열을 입력받고 해당 수열의 수를 각각 위에서 정의한 Bianry함수에 넣고 결과를 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, M;
vector<int> A, B;
int Binary(int i)
{
int left = 0;
int right = A.size() - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (i == A[mid]) return 1;
else if (i > A[mid]) left = mid + 1;
else if (i < A[mid]) right = mid - 1;
}
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
A.assign(N, 0);
for (int i = 0; i < N; i++) cin >> A[i];
sort(A.begin(), A.end());
cin >> M;
B.assign(M, 0);
for (int i = 0; i < M; i++) cin >> B[i];
for (auto b : B) cout << Binary(b) << '\n';
}
후기
while문을 깨는 조건을 정하는데 고민 좀 했지만 이분탐색의 흐름을 따라가 보면 찾고자 하는 값이 없을 때 범위가 뒤집혔다. 그래서 left는 당연히 작아야 하고 둘이 같아도 수가 비교는 가능하기에 이를 고려해 설정했다.
left right 갱신해줄 때 중간값 +1, -1을 처음에 안하고 했다. 무한루프에 빠져 찾다가 알았다. 만약 left가 0 right가 1이면 중간값이 0이 계속 나와 오류가 생긴다.
이분 탐색은 쉽게 구현 했지만 디테일이 아쉬웠다.
