[개념] 이분검색 / c / 제한시간 없음

▣ 입력설명

임의의 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

 

<코드>

#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>

int compare(const void* n1, const void* n2) {
	if (*(int*)n1 > * (int*)n2)
		return 1;
	else if (*(int*)n1 < *(int*)n2)
		return -1;
	else return 0;
}
int num[1000000];
int main() {
	int lt = 0, rt, mid;
	int n, m, i, j;


	scanf("%d %d", &n, &m);
	for (i = 0; i < n; i++) {
		scanf("%d", &num[i]);
	}
	rt = n - 1;
	qsort(num, n, sizeof(int), compare);

	while (1) {
		mid = (rt + lt) / 2;
		if (num[mid] == m) break;
		else if (num[mid] < m) {
			lt = mid + 1;
		}
		else
			rt = mid - 1;
	}
	
	printf("%d\n", mid + 1);

	return 0;
}

 

이분 검색이란 배열의 범위를 반으로 줄여가면서 원하는 값을 찾아가는 것이다.

 

우선 문제에서 수를 정렬하기 위해서 qsort를 사용했다.

 

입력 예시를 예로들면, 정렬된 배열은 다음과 같다

 

0	1	2	3	4	5	6	7
12	23	32	57	65	81	87	99

 

배열의 처음과 끝을 각각 lt(left), rt(right)로 선언을 한 후, mid는 lt와 rt의 중간값을 나타낸다 (mid= (lt + rt) / 2)

 

0, lt	1	2	3, mid	4	5	6	7, rt
12	23	32	57	65	81	87	99

 

while문에서는 원하는 값이 m보다 크다면 반드시 num[mid]보다 오른쪽에 있기 때문에 lt를 mid+1의 자리로 바꿔준다

                                                 ----->

0	1	2	3	4, lt	5, mid	6	7, rt
12	23	32	57	65	81	87	99

 

만약 m보다 작다면 반드시 num[mid]보다 왼쪽에 있기 때문에 rt를 mid-1의 자리로 바꿔준다

                                    

0, lt	1, mid	2,rt	3	4	5	6	7
12	23	32	57	65	81	87	99

 

num[mid]가 m과 같을때 break문을 걸어주고 출력값은 배열의 위치 이기 때문에 mid+1이 된다.