이진 검색 알고리즘(Binary Search)

이진 검색 알고리즘

 

이진 검색은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘 이다.

이 알고리즘을 적용하는 전제 조건은 데이터가 키 값으로 이미 정렬 되어 있어야 한다.
그리고 이진검색은 선형 검색보다 좀 더 빠르게 검색 할 수 있다는 장점이 있다.

이진 검색 알고리즘의 종료 조건

1. 중간 인덱스의 값이 key와 일치하는 경우.
2. 검색 범위가 더 이상 없는 경우

 

구글에서 퍼온 사진

이렇게 길이가 10인 배열에서 46을 찾는다고 해보자.

 

1. 가장 처음으로는 0과 9의 중간값인 4번 인덱스를 검사한다.

2. 우리가 찾는 숫자는 46이기 때문에 4번 인덱스의 값 32는 키 값 보다 작다.

3. 그러므로 우리는 중간인덱스 앞의 값들은 검사를 안해도 상관 없다고 확신을 할 수 있다.(정렬이 되어있다면)

4. 그래서 최소 인덱스를 중간값 +1로 설정해준다.

5.이제 5번 인덱스와 0번 인덱스 중간값인 7번인덱스의 값을 키값과 비교한다.

6. 우리가 찾는 46보다는 크기때문에 최대값은 중간값 -1을 해준다.

7. 최소 인덱스 값은 5가 되었고, 최대 인덱스 값은 6이 되었다.

8. 5번 인덱스와 6번 인덱스의 중간값인 5번 인덱스를 검사하여 46을 찾아냈다.

 

 

이런식으로 중간값을 검사하여 키값과 비교해서 판단하고 범위를 줄여나간다.

이 과정 안에서 키값이 있으면 성공이고

만약 최소인덱스가 최대 인덱스보다 커져버린다면 실패다.

 

바로 코드로 알아보자

 

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

//int형 배열 a, 배열 요소 개수 n , 찾을 키값
int Search(const int a[], int n, int key)
{
	int pl = 0; //배열의 맨 처음 인덱스
	int pr = n - 1; //배열의 마지막 인덱스
	int pc; //검색 한가운데의 인덱스

	do {
		pc = (pl + pr) / 2;  //계산으로 중앙 인덱스를 구해줌
		if (a[pc] == key)
		{
			return pc;	//중앙값이 key값과 같다면 성공
		}
		else if (a[pc] < key)
		{
			//키값이 중앙 인덱스 값 보다 크기때문에 최소인덱스를 중앙값 다음으로 바꿔줌
			pl = pc + 1;
		}
		else
		{
			//키값이 중앙 인덱스 값 보다 작기때문에 최대인덱스를 중앙값에서 -1을 해줌.
			pr = pc - 1;
		}
	} while (pl <= pr);
	//최소 인덱스가 최대 인덱스보다 작을때까지만 loop
	//즉 최소 인덱스값이 최대 인덱스값보다 커져버리면 실패

		return -1;
	
}


int main(void)
{
	int i, nx, ky, idx;
	int* x;
	puts("이진 검색");
	printf("요소 개수 : ");
	scanf_s("%d", &nx);
	x = calloc(nx, sizeof(int));
	printf("오름차순으로 입력하세요\n");
	printf("x[0] : ");
	scanf_s("%d", &x[0]);  //처음 인덱스값을 먼저 입력받음

	for (i = 1; i < nx; i++)
	{
		do {
			printf("x[%d] : ", i);
			scanf_s("%d", &x[i]);
		} while (x[i] < x[i - 1]); //오름차순이기 때문에 앞 인덱스보다 클때까지 loop
	}

	printf("검색 값: ");
	scanf_s("%d", &ky);
	idx = Search(x, nx, ky);
	if (idx == -1)
	{
		puts("검색에 실패하였습니다.");
	}
	else
	{
		printf("%d는(은) x[%d]에 있습니다.\n", ky, idx);
	}

	free(x);

	return 0;

}

 

Search 함수를 보면 do while문으로 계속 검사하면서 검사 범위를 줄여나간다.

 

전제조건이 정렬이 되어있는 값들이기 때문에,

메인함수에서 요소의 값들을 입력받을때도 전 인덱스보다 클때까지 반복시키며 입력을 받는다.

Search함수의 리턴값으로 검색결과를 알려주고 할당했던 메모리를 해제 시켜주며 끝낸다.

 

한번도 써본적 없는 방식인데 , 정렬된 값에서 검색을 할거라면 이 알고리즘을 이용해도 너무 좋을것같다.