42. 이분검색 (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★☆☆☆☆

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n, m, low, high;
	scanf("%d %d", &n, &m);
	
	vector<int> num(n+1,0);
	
	for(int i = 1; i < num.size(); i++)
		scanf("%d", &num[i]);
	
	sort(num.begin(), num.end());
	low = 1;
	high = n;
	
	int mid = (low + high) / 2;
	while(num[mid] != m)
	{
		mid = (low + high) / 2;
		if(num[mid] > m)
			high = mid -1;
		else if(num[mid] < m)
			low = mid + 1;
	}
	
	printf("%d", mid);
	
	return 0;
}

1. 이분검색을 통한 특정 원소의 인덱스를 구하는 방법을 사용했다. 이분검색은 반드시 오름차순으로 정렬된 vector 나 배열에서 사용해야한다.

23

87

65

12

57

32

99

81

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

↓

    low ↓                                                              mid  ↓  (3.5 => 3(int))                                                               high ↓

12

23

32

57

65

81

87

99

32 < 57 이므로 high = mid + 1 = 4

 

    low ↓                                       mid  ↓  (2(int))                        high ↓

12

23

32

57

65

81

87

99

찾으려는 숫자를 찾았으므로 mid + 1 = 3

1을 더하는 이유는 3번째로 작은 수 이기 때문