42. 이분 탐색

문제

임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요.

입력설명

첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다. 두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

출력설명

첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.

입력예제

8 32
23 87 65 12 57 32 99 81

출력예제

3

---

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
	//freopen("input.txt", "rt", stdin);
	int n, key, left=0, right, i, mid, result;
	scanf("%d %d", &n, &key);
	vector<int> check(n);
		
	for(i=0; i<n; i++){
		scanf("%d", &check[i]);
	}
	sort(check.begin(), check.end());
	
	right = n-1;
	
	while(left <= right){
		mid = (left+right)/2;
		if(key == check[mid]){
			printf("%d", mid+1);
			return 0;
		} else if(key < check[mid]){
			right = mid-1;
		} else {
			left = mid+1;
		}
	}
	
	return 0;
}

이분탐색은 완전탐색과 달리 반을 쪼개서 크냐 작냐 같냐를 비교하는 탐색입니다.

이를 하기 위해서는 left, mid, right가 필요하고 첫 시작에 left = 0일수밖에 없기에 0으로 초기화합니다.
right = 배열의 크기 -1
mid = (left + right)/2초기화하고 while문으로 left가 right보다 커지는 순간에 끝나게 세팅합니다 만약 저렇게 된다면 찾는 값이 배열에 존재하지않는것이므로 필요에의해 print를 할수도 있겠죠