이분검색

▣ 입력설명

임의의 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 main() {
	int N, M;
	int i, j, temp;

	scanf("%d %d", &N, &M);
	int* arr = malloc(sizeof(int) * N);
	for (i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}

//버블 정렬
	for (i = 0; i < N; i++) {
		for (j = 0; j < i; j++) {
			if (arr[i] < arr[j]) {
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}

	int inx = N / 2;
	int answer=-1;
	while (inx != 0 || inx > N) {
		if (arr[inx] == M) {
			answer = inx + 1;
			break;
		}
		else if (arr[inx] > M) inx = inx / 2;
		else inx = inx + inx / 2;
	}

	printf("%d", answer);

	return 0;
}

 

 

<전상일씨 코드>

 

#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라는 퀵 정렬함수를 사용한걸 볼 수 있다.

rt와 lt를 사용해서 코드를 작성했다. 

 

 

chonstudyroom.tistory.com/24

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