Chap5-2탐색

1. 이진탐색

1) 개념

"데이터가 정렬된 상태에서" 원하는 값을 찾아내는 알고리즘
대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄여나가는 것
시간복잡도: O(logN)

2) 대표코드

이진 탐색과정

• 현재 데이터의 중앙값 선택
• 중앙값>타깃값 -> 중앙값 기준 왼쪽 데이터셋 선택
  중앙값<타깃값 ->중앙값 기준 오른쪽 데이터셋 선택
• 반복하다가 중앙값=타깃값 -> 종료

while (s <= e) {
	int middle= (s + e) / 2;
	if (input[middle] > num) {
		e = middle-1;
	}
	else if (input[middle] < num) {
		s = middle + 1;
	}
	else {
		found = true;
		break;
	}
}

3) 문제: 원하는 정수 1920번

1. 문제: https://www.acmicpc.net/problem/1920
   

2. 코드

#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> input(n,0);
	for (int i = 0; i < n; i++) {
		cin >> input[i];
	}
	sort(input.begin(), input.end());

	cin >> m;
	for (int i = 0; i < m; i++) {
		int num;
		cin >> num;
		int s = 0; int e = input.size() - 1;
		bool found = false;

		while (s <= e) {
			int middle= (s + e) / 2;
			if (input[middle] > num) {
				e = middle-1;
			}
			else if (input[middle] < num) {
				s = middle + 1;
			}
			else {
				found = true;
				break;
			}
		}
		if (found) cout << 1 << "\n";
		else cout << 0 << "\n";
	}

	return 0;
}

**4) 문제: 기타레슨 2373번

1. 문제: https://www.acmicpc.net/problem/2343
   

2. 코드

**5) 문제: 기타레슨 2373번

1. 문제: https://www.acmicpc.net/problem/1300