[백준 - 1920] 수 찾기(feat. 이진탐색 알고리즘) / C++

출처 => 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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

 

 

사고의 흐름

▶ 선형탐색을 통해 쉽게 구현할 수 있지만 그렇게 하게 되면 런타임에러가 발생한다! 그래서 보다 더 빠르게 탐색하는 이진탐색 알고리즘을 이용하였다. 

 

▶ 1가지의 포인트를 잡으면 될 것 같다!

 

>> 첫 번째 포인트! 중앙값을 중심으로 쪼갠다.

▶ 찾고자 하는 값을 key라고 하자. 맨 첫 번째 인덱스를 start(0)이라고 하고, 맨 마지막 인덱스를 end(n-1)로 한 뒤, 중앙값의 인덱스를 mid((s+e)/2)라고 선언하였다. 

▶ arr배열의 중앙값인 arr[mid]이 key값과 같은가, 큰가, 작은가를 기준으로 if문을 이용해 경우를 나눈다. 같으면 1을 출력하고, 크거나 작다면 배열을 start와 end의 값을 이동하여 변경하여 준다!

 

 

소스코드 및 실행결과

#include<iostream>
#include<algorithm>//sort함수 사용하기 위해
using namespace std;

int n, m;
int arr[1001];

void binarySearch(int key) {
	int start = 0;
	int end = n - 1;
	int mid;

	while (end >= start) {

		mid = (start + end) / 2;
		//mid는 start와 end의 중앙값
		if (arr[mid] == key) {
			//만약 중앙값이 찾고자 하는 값과 같다면
			cout << 1 << endl;//1을 출력
			return;//종료
		}
		else if (arr[mid] > key) {
			//만약 중앙값이 찾고자 하는 값보다 크다면
			end = mid - 1;
			//중앙값보다 앞에 있는 것들로 다시 이진탐색 ㄱㄱ
		}
		else {
			start = mid + 1;
		}
	}
	cout << 0 << endl;
	//만약 이렇게까지 했는데도 찾고자 하는 값이 나오지 않으면 0을 출력
	return;//종료
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	//입출력을 빠르게 하기 위해
	
	cin >> n;//찾고자 하는 배열의 크기 입력

	int temp;//입력할 값

	for (int i = 0; i < n; i++) {
		cin >> temp;
		arr[i] = temp;
		//입력한 값을 arr배열에 담는다.
	}

	sort(arr, arr + n);//순서대로 정렬

	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> temp;
		binarySearch(temp);
		//숫자를 넣어주고 넣는 족족 바로 arr배열을 대상으로 이진탐색을 실행하여 0또는1을 출력
	}
	return 0;
}

 

의견 및 반성

if (arr[mid] == key) {
			cout << 1 << endl;
			return;
		}

▶ 이 부분을 놓친 것 같다. 자세히 말하면 return을 놓쳤다. return 문을 작성하지 않아 while문이 끝나면 아래에 작성한 cout<<0<<endl; 구문 때문에 무조건적으로 0이 출력이 되었다. 상황이 종결되었을 때, 더 이상 구문을 돌릴 필요가 없어졌을 때 return을 적절히 사용해야겠다. 좋은 교훈!