이진 탐색

이진 탐색은 데이터가 정렬된 상태에서 원하는 값을 찾아내는 알고리즘이다.

개상 데이터의 중간값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는게 핵심이다.

 

이진 탐색은 주로 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 알고리즘임을 알아두자.

 

이진 탐색 과정

1. 현재 데이터셋의 중앙값을 선택

2. 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택

3. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택

4. 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색 종료

 

백준 - 1920: 트리의 지름 구하기

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

나의 코드(오류 수정 & 피드백)

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

static vector <int> num;
// static vector <int> num_f;

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, n_f, num_f;
	int n1, n2;

	cin >> n;
	num.resize(n + 1);

	for (int i = 1; i <= n; i++) {
		cin >> n1;
		num[i] = n1;
	}

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

	cin >> n_f;

	for(int i = 1; i <= n_f; i++) {

		cin >> num_f;
		bool find = false;
		int s = 1, e = n;
		int mid = (n + s) / 2;

		while(s <= e) {

			mid = (s + e) / 2;

			if (num_f > num[mid]) { // 중앙값 < 타깃 데이터

				s = mid + 1;

			}

			else if (num_f < num[mid]) { // 중앙값 > 타깃 데이터

				e = mid - 1;
			
			}

			else { // 중앙값 == 타깃 데이터
				find = true;
				break;
			}

		}
		if (find == true) {
			cout << '1' << endl;
		}
		else {
			cout << '0' << endl;
		}
	}

}