07. 순차 탐색과 이진 탐색

순차 탐색의 방법

• Sequential Search는 특정한 원소를 찾기 위해 원소를 순차적으로 하나씩 탐색하는 방법
• 찾은 뒤 해당 인덱스를 반환

순차 탐색의 구현

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LENGTH 1000

char** array;
int founded;

// 순차 탐색
int main(void) {
	int n;
	char* word;
	word = malloc(sizeof(char) * LENGTH);
	// 총 문자열의 갯수와 찾을 이름 입력
	scanf("%d %s", &n, word);
	array = (char**)malloc(sizeof(char*) * n);
	// 문자열 순서대로 입력
	for (int i = 0;i < n;i++) {
		array[i] = malloc(sizeof(char) * LENGTH);
		scanf("%s", array[i]);
	}
	// 순차적으로 탐색
	for (int i = 0;i < n;i++) {
		if (!strcmp(array[i], word)) {
			printf("%d번째 원소입니다.\n", i + 1);
			founded = 1;
		}
	}
	if (!founded) printf("원소를 찾을 수 없습니다.\n");
	system("pause");
	return founded;
}

정렬 유무에 상관없이 앞의 원소부터 확인하기 때문에 O(N)의 시간 복잡도를 가짐

이진 탐색의 방법

• 배열 내부 데이터가 이미 정렬 되어 있는 상황에서 사용 가능한 알고리즘
• 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징

이진 탐색의 구현

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX_SIZE 100000

int a[MAX_SIZE];
int founded = 0;

int search(int start, int end, int target) {
	if (start > end) return -9999;
	int mid = (start + end) / 2;

	if (a[mid] == target) return mid;
	else if (a[mid] > target) return search(start, mid - 1, target);
	else return search(mid + 1, end, target);
}

int main(void) {
	int n, target;
	scanf("%d %d", &n, &target);

	for (int i = 0;i < n;i++) scanf("%d", &a[i]);
	int result = search(0, n - 1, target);

	if (result != -9999) printf("%d번째 원소입니다.\n", result + 1);
	else printf("원소를 찾을 수 없습니다.\n");
	system("pause");
	return 0;
}

확인 할 때마다 원소의 개수가 절반씩 줄어들어 탐색시간이 O(log N)의 시간 복잡도를 가짐