[알고리즘] 탐색(2) - 이진 탐색

 

이진 탐색(Binary Search)

이진 탐색

• 정렬된 데이터에서 사용할 수 있다.
• 탐색 범위를 절반씩 줄여가면서 원하는 데이터를 찾는 방식이다.

 

탐색 과정

1. 데이터 중앙에 있는 요소 선택
2. 선택된 중앙 요소가 목표값인지 확인
3. 목표값보다 작으면 왼쪽 부분에서, 목표값보다 크면 오른쪽 부분에서 이진 탐색을 한다.
4. 목표값을 찾을 때까지 1~3번을 반복

이진 탐색 과정

이진탐색의 성능

• 데이터 크기: n
• 탐색 반복 횟수: x
• 이진 탐색은 탐색을 반복할 수록 데이터 크기가 절반(1/2)씩 줄어든다.

$$데이터\;크기 * (1/2)^{탐색\;반복\;횟수} = 데이터\;범위$$

 

최악의 경우

• 데이터 범위가 1까지 오는 상황

$$n * (1/2)^x = 1$$

$$=> n=2^x$$

$$=> x=log_2{n}$$

 

따라서 시간 복잡도는 O(logN)

 

 

[코드 - C]

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

int binarySearch(int data[], int size, int target)
{
	int left, mid, right;

	left = 0;
	right = size - 1;

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

		if (target == data[mid])
			return mid;
		else if (target > data[mid]) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}

	return -1;
}

int Compare(const void* a, const void* b)
{
	// a가 크면 양수
	// b가 크면 음수
	// 같으면 0
	return (*(int*)a - *(int*)b);
}

void printResult(int data[], int length) 
{
	for (int i = 0; i < length; i++) {
		printf("%d ", data[i]);
	}
	printf("\n");
}

int main(void) {

	int data[] = {54, 74, 2939, 39548, 109, 284, 394, 585, 3847, 728, 11, 838, 999, 294};
	int length = sizeof(data) / sizeof(data[0]);
	int target = 2939;

	printf("목표값: %d\n", target);

	printf("before sort\n");
	printResult(data, length);
	// 퀵 정렬
	qsort((void*)data, length, sizeof(int), Compare);
	printf("after sort\n");
	printResult(data, length);
	
	// 탐색
	int found = binarySearch(data, length, target);
	if (found != -1) {
		printf("찾은 인덱스:%d\n", found);
		printf("찾은 값:%d\n", data[found]);
	}
	else {
		printf("탐색 실패\n");
	}
	
	


	return 0;
}