Chater 6-1 이진 탐색(Binary Search)

홍정모 교수님의 강의 홍정모의 따라하며 배우는 C언어(부록) 를 듣고 정리한 필기입니다. 😀
ppt 캡처는 모두 교수님 강의에서 캡처한 것임을 밝힙니다.

Chapter 6. Binary Search

🚀 탐색

🔥 순차 탐색

처음부터 끝까지 차례대로 하나씩 다 순회하면서 찾아봐야 함.

🔥 이진 탐색

1. 정렬이 되어 있어야 한다는 전제가 있어야 한다.
   • 정렬 시간 소모가 있기 때문에 탐색하는 횟수가 적거나 탐색 범위가 작으면 순차 탐색하는게 더 나을 수도 있다.
   • 그러나 이런게 아니면 이진 탐색이 더 효율이 좋다. 최악의 경우라도 logN 번을 넘기지 않기 때문이다. (순차 탐색은 최악의 경우 끝까지 찾는 N번)
2. 아래 과정을 Key를 찾거나 모두 탐색하라 때 까지 반복한다.
3. 배열의 가운데 위치를 찾은 후 그 가운데 위치의 값과 Key 를 크기 비교 한다.
4. 찾으려는 Key 가 가운데 위치의 값보다 크다면 오른쪽 범위로, 그 반대라면 왼쪽 범위로 간다. 찾으려는 범위가 점점 절반씩 줄어든다.

📜코드 구현

#include <stdbool.h>

#define TMAX 40

typedef struct {
	char character[TMAX];
	char name[TMAX];
}Item;

void print_item_array(Item items[], int size)
{
	for (int i = 0; i < size; ++i)
		printf("%s (%s)\n", items[i].character, items[i].name);
	printf("\n");
}

// sorting 할 때 필요한 비교 함수
int compare_items(const void* first, const void* second) 
{
	Item* first_item = (Item*)first;
	Item* second_item = (Item*)second;

	return strcmp(first_item->character, second_item->character);
}

// 순차 탐색
const Item* sequential_search(const Item items[], const int size, const char key[TMAX])
{
	for (int i = 0; i < size; ++i)
		if (strcmp(items[i].character, key) == 0)
			return &items[i];

	return NULL;
}

// 이진 탐색
const Item* binary_search(const Item items[], const int size, const char key[TMAX])
{
	int first = 0;
	int last = size - 1;
	int middle = (first + last) / 2;

	while (first <= last) { // first > last 가 되면 다 찾았다는 것. 즉, 모두 탐색하는 동안 key 못 찾음. 없음!
		int comp = strcmp(items[middle].character, key); // 0이면 일치, -1이면 오른쪽 파라미터가 더 큼, 1이면 오른쪽 파라미터가 더 작음.

		if (comp < 0) // 오른쪽 범위로
			first = middle + 1;
		else if (comp == 0) // 찾았음
			return &items[middle];
		else // 왼쪽 범위로
			last = middle - 1;

		middle = (first + last) / 2;
	}

	return NULL;
}

#include <stdio.h>
#include <string.h>

int main()
{
	Item items[] = {
		{"Iron Man", "Tony Stark"},
		{"Thor", "Thor Odinson"},
		{"Ant-Man", "Hank Pym"},
		{"Wasp", "Janet van Dyne"},
		{"Hulk", "Bruce Banner"},
		{"Captain America", "Steve Rogers"},
		{"Scarlet Witch", "Wanda Maximoff"},
		{"Black Widow", "Natacha Romanoff"},
		{"Dr. Strange", "Stephen Strange"},
		{"Daredevil", "Matthew Murdock"},
		{"Punisher", "Frank Castle"},
		{"Batman", "Bruce Wayne"}
	};

	int n = sizeof(items) / sizeof(items[0]);

	print_item_array(items, n);
	qsort(items, n, sizeof(Item), compare_items); // 이진 탐색을 위해선 정렬 필수
	print_item_array(items, n);

	while (1) {
		char key[TMAX] = "";
		printf("Input Key >> ");

		fgets(key, TMAX, stdin);
		int len = strlen(key);
		if ((strlen(key) > 0) && (key[strlen(key) - 1] == '\n'))
			key[strlen(key) - 1] = '\0';

		if (strcmp(key, "exit") == 0)
			break;

		const Item* found = binary_search(items, n, key);

		if (found == NULL)
			printf("Not in the list.\n\n");
		else
			printf("%s is %s\n\n", found->character, found->name);
	}
}

💎출력💎

Iron Man (Tony Stark)
Thor (Thor Odinson)
Ant-Man (Hank Pym)
Wasp (Janet van Dyne)
Hulk (Bruce Banner)
Captain America (Steve Rogers)
Scarlet Witch (Wanda Maximoff)
Black Widow (Natacha Romanoff)
Dr. Strange (Stephen Strange)
Daredevil (Matthew Murdock)
Punisher (Frank Castle)
Batman (Bruce Wayne)

Ant-Man (Hank Pym)
Batman (Bruce Wayne)
Black Widow (Natacha Romanoff)
Captain America (Steve Rogers)
Daredevil (Matthew Murdock)
Dr. Strange (Stephen Strange)
Hulk (Bruce Banner)
Iron Man (Tony Stark)
Punisher (Frank Castle)
Scarlet Witch (Wanda Maximoff)
Thor (Thor Odinson)
Wasp (Janet van Dyne)

Input Key >> Batman
Batman is Bruce Wayne

Input Key >> slkdlskdl
Not in the list.

Input Key >> exit

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

DataStructure2 카테고리 내 다른 글 보러가기