[ Algorithm ] Binary Search

devK08·2024년 10월 7일

알고리즘

Algorithm

목록 보기

3/6

WHAT is Binary Search?

이분 탐색은 계속 두개로 분할하여 탐색하는 탐색기법입니다.

이분 탐색을 사용하기 위해서는 어떤 리스트가 정렬되어 있는 상태여야합니다.

Why Binary Search?

이분 탐색을 쓰는 이유는 시간복잡도가 순차탐색 알고리즘보다 매우 짧게 들기 때문이다.

순차탐색 알고리즘은 순차적으로 탐색하는 탐색기법이다.

순차탐색의 시간복잡도는 O(N)이고, 이분탐색의 시간복잡도는 O(log(n)) 이다.

왜 O(log(n))임?

이런식으로 로드하기 때문에 O(log(n))이 걸리는데, 예를 들어 10개의 숫자가 있는 배열이 있다고하면,

log2 10 = n이랑 2^n = 10이랑 이 n들이 갔기 때문에 계속 2씩 들어가면서 log2 n만에 찾을 수 있는 것이다.

CODE

// 이진 탐색 알고리즘

#include <stdio.h>
int arr[100]; // 배열 선언

int search(int st, int end, int key) { // search 함수
	if(st<=end) { // st가 end를 안넘어가면
		int mid = (st+end) / 2; // mid 인덱스를 구함
		if(key==arr[mid]) return 1; // key값과 같으면 1 리턴
		else if(key>arr[mid]) search(mid+1, end, key); // key값이 더 크면 mid+1 부터 end까지 탐색을 다시
		else search(st, mid-1, key); // 아니면 st 부터 mid-1까지 탐색을 다시
	}
	else return 0; // 넘어가면 못 찾음.
}

int main()
{
	for(int i=0;i<100;i++) {
		arr[i]=i+1;
	}
	// 1 ~ 100까지 배열
	int n;
	scanf("%d", &n);
	if(!search(0, 99, n)) printf("Not Found"); // 못 찾으면 Not Found
	else printf("Found"); // 찾으면 Found	
	return 0;
}