1920 수 찾기(이분탐색)

백준 1920번 수찾기 : https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

[개념]

이분탐색 : (정렬된 리스트에서) 탐색범위를 절반으로 좁혀가며 데이터를 탐색하는 방법

 - 이진탐색, Binary search 라고도 한다. 

 

예시로,

상대방의 0~100 까지 숫자 중 생각해둔 숫자를 맞출 때, 내가 말한 숫자에 대해 up down을 해주면 범위를 점점 좁혀가며 숫자를 맞추는 경우가 있다.

여기서, 확률적으로 빠르게 맞출 수있는 방법은 처음에는 50, 그리고 up down에 따라 범위를 좁히고 다시 그 값의 절반 값을 이야기하는 것이다. 

 

 

이것을 

위 그림과 같이, 정렬된 리스트에서 특정 값을 찾기 위해서

low high에서 중간 값인 mid를 찾으려는 값과 비교하고, 값이 큰지 작은지에 따라 low high를 조정하며 값을 탐색한다.  

high > low가 되면, 해당 리스트에는 찾는 값이 없음을 의미한다. (더 찾을 값이 없음)

 

 

[문제풀이]

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	cin >> n;
	vector<int> a;
	a.reserve(n);
	for (int i = 0; i < n; i++) {
		int k;
		cin >> k;
		a.push_back(k);
	}
	sort(a.begin(), a.end());


	cin >> m;
	int b, s, k;
	for (int i = 0; i < m; i++) {
		cin >> b;
		s = 0;
		k = n - 1;
		
		while (k >= s)  ; 탐색
		{
			int m = (k + s) / 2;

			if (a[m] == b) {
				cout << "1" << '\n';
				break;
			}
			else if (a[m] > b) {
				k = m - 1;
			}
			else {
				s = m + 1;
			}
		}

		if (k < s) {
			cout << "0" << '\n';
		}
	}
	
}

vector<int> a	n개의 정수를 저장하기 위한 vector
	reserve(n)	하지 않으면 메모리 초과
	sort(a.begin(), a.end())	이분탐색을 위해 미리 정렬
int k, s	k :  현재 탐색범위에서 가장 큰 값 s :  현재 탐색범위에서 가장 작은 값
while(k>=s) {}	① 현재 범위의 중간 값을 찾아 m에 저장 ② 중간 값을 찾으려는 값(b)과 비교  - 같으면 : 1 출력하고 반복문 빠져나오기  - 중간 값이 더 크면 : 탐색 범위에서 가장 큰 값을 m-1로 변경  - 중간 값이 더 작으면 : 탐색 범위에서 가장 작은 값을 m+1로 변경 ③ k < s 면, 찾는 값이 없는 것. 따라서 0 출력

 

 

[comment]

약 1-2년전 스터디하며 풀었던 문제라서 풀이 전 정리한게 없다. 

메모리초과 때문에 고생했던 기억, reserve()로 해결했다.

또 시간초과가 나서 왜지 했는데, 함수로 선언해서 그런거였음 main에 루프만드니 해결됐다. 하지만, 재귀함수는 또 가능할 것 같다. 

 

이 문제는 딱 이분탐색에 대해 익히기 좋은 문제인듯하다.