[사전] 이진탐색(재귀, 비재귀, 숫자맞추기)

이진탐색 - 재귀 버전

 

- x ≤ k 를 만족하는 사전의 키 x 중 가장 큰 값의 위치(즉, 인덱스) 출력

(위치는 0부터 시작한다고 가정하고, 위 조건을 만족하는 x가 없는 경우 –1 출력)
- 즉, 키 k가 존재하는 경우에는 k의 위치를 출력하면 되고, 그렇지 않은 경우 k보다 작으면서 가장 큰 수의 위치를 출력하면 된다.

 

입력 예시 1
8 -7 ↦ n = 8, k = –7

출력 예시 1
-92 -31 -7 4 14 20 29 44
□2 ↦ 사전에서 -7의 위치는 2

입력 예시 2
8 33 ↦ n = 8, k = 33

출력 예시 2
-92 -31 -7 4 14 20 29 44
□6 ↦ 문제 조건을 만족하는 사전의 키는 29이고, 사전에서 29의 위치는 6

 

#include <stdio.h>
#include <stdlib.h>

int n;// 배열 크기
int* D;//사전
int t;

int rFE(int k, int left, int right) {
	int mid;

	if (left > right)
		return -1;

	mid = (left + right) / 2;
	if (k == D[mid])
		return mid;
	else if (k < D[mid])
		return rFE(k, left, mid - 1);
	else {// if(k > D[mid])
		t = mid;
		return rFE(k, mid + 1, right);
	}

}

int findElement(int k) {
	return rFE(k, 0, n-1);
}

int main() {
	int k;// 탐색할 키 k
	int result;
	scanf("%d %d", &n, &k);

	D = (int*)malloc(n * sizeof(int));

	for (int i = 0; i < n; i++) {
		scanf("%d", &D[i]);
		getchar();
	}

	result = findElement(k);

	if (result == -1) {
		if (t != NULL)
			printf(" %d", t);
		else
			printf(" %d", result);
	}
	else
		printf(" %d", result);

	return 0;
}

 

 

이진탐색 - 비재귀 버전

 

출력 (문제 1과 약간 다름에 주의)
- x ≥ k 를 만족하는 사전의 키 x 중 가장 작은 값의 위치(즉, 인덱스) 출력
(위치는 0부터 시작한다고 가정하고, 위 조건을 만족하는 x가 없는 경우 n 출력)

 

입력 예시 1
8 -100 ↦ n = 8, k = -100
-92 -31 -7 4 14 20 29 44

출력 예시 1
□0 ↦ 문제 조건을 만족하는 사전의 키는 -92이고, 사전에서 -92의 위치는 0

입력 예시 2
8 55 ↦ n = 8, k = 55
-92 -31 -7 4 14 20 29 44

출력 예시 2
□8 ↦ 55보다 큰 사전의 키는 없음

 

#include <stdio.h>
#include <stdlib.h>

int n;// 배열 크기
int* D;//사전
int t = -999999;

int findElement(int k) {
	int left = 0;
	int right = n - 1;
	int mid;

	while (left <= right) {
		mid = (left + right) / 2;

		if (k == D[mid])
			return mid;
		else if (k < D[mid]) {
			t = mid;
			right = mid - 1;
		}
		else {// if(k > D[mid])
			left = mid + 1;
		}
	}

	return -1;
}

int main() {
	int k;// 탐색할 키 k
	int result;
	scanf("%d %d", &n, &k);

	D = (int*)malloc(n * sizeof(int));

	for (int i = 0; i < n; i++) {
		scanf("%d", &D[i]);
		getchar();
	}

	result = findElement(k);

	if (result == -1) {
		if (t == -999999)
			printf(" %d", n);
		else
			printf(" %d", t);
	}
	else
		printf(" %d", result);

	return 0;
}

 

 

이진탐색을 응용한 숫자 맞추기 게임 (비재귀 방식 사용함)

 

- 친구는  k > m 인지, Y(예)/N(아니오)으로 알려준다. (여기서 m은 a와 b사이의 중간값으로, m =(a + b)/2이다. 는 내림 기호)
- 답이 Y인 경우, m + 1 ≤ k ≤ b 이므로 a의 값을 m + 1로 바꾼다.
- 답이 N인 경우, a ≤ k ≤ m 이므로 b를 m으로 바꾼다.

 

입력 예시 1
10 20 3 ↦ a = 10, b = 20, Y/N의 개수 3개
NNY

출력 예시 1
12 ↦ k = 12

입력 예시 2
1 1000 10 ↦ a = 1, b = 1000, Y/N의 개수 10개
NYYNYNYYNY

출력 예시 2
421 ↦ k = 421

 

#include <stdio.h>
#include <stdlib.h>

//비재귀

int findElement(int a, int b, int num, char str[]) {
	int mid;
	int k = 0, i = 0;

	while(1) {
		mid = (a + b) / 2;

		if (a == b) {
			k = mid;
			break;
		}

		if (str[i] == 'Y') {
			a = mid + 1;
		}
		else {
			b = mid;
		}
		i++;
	}

	return k;
}

int main() {
	int a, b, num;// a, b 값, Y/N의 갯수
	char str[1000];
	int k = 0;

	scanf("%d %d %d", &a, &b, &num);

	scanf("%s", str);

	k = findElement(a, b, num, str);
	printf("%d", k);

	return 0;
}