이진 탐색(Binary Search) 알고리즘 개념과 예제

이진 탐색

이진 탐색은 오름차순으로 정렬되어있는 데이터에서 원하는 값(타겟 넘버)의 위치를 찾아내는 알고리즘이다.

여기서 이진(Binary)는 우리가 알고있는 그 이진 코드 (0101001...) 가 아니라

데이터를 반(2개)으로 나누어서 비교하고 찾는 방식이여서 이진 탐색이라고 한다.

이진 탐색의 알고리즘 진행방식은 아래와 같다.

1.  정렬되어있는 데이터의 중간 값을 임의의 값 X로 정함
2.  타겟 넘버의 값과 X를 비교
3.  타겟 넘버의 값이 X보다 크다면, 타겟 넘버는 데이터에서 X보다 우측에 위치해 있으니 반으로 나눈 데이터의 우측에서 1번 과정부터 다시 시작
4.  타겟 넘버의 값이 X보다 작다면, 타겟 넘버는 데이터에서 X보다 좌측에 위치해 있으니 반으로 나눈 데이터의 좌측에서 1번 과정부터 다시 시작

 

이진 탐색 예시

아래와 같은 데이터가 있다고 가정하자.

1

5

6

8

10

16

25

33

 

여기서 찾고싶은 값(타겟 넘버)은 25일 때

임의의 값 X를 정하기 위해서 데이터의 중간 값인 8을 X로 정한다.

1

5

6

8

10

16

25

33

 

이제 타겟 넘버와 X를 비교하였을 때,

X = 8 < 타겟 넘버 = 25

타겟 넘버인 25가 X인 8보다 더 크기 때문에 정렬된 데이터에서 25는 8보다 우측에 있다는 것이 정해졌다.

1

5

6

8

10

16

25

33

 

그럼 데이터에서도 비교해야 될 대상이 반으로 줄어들 것이다.

10

16

25

33

 

이제 X를 수정해야 한다.

현재 비교해야할 데이터의 중간 값인 16을 X의 값으로 정한다.

10

16

25

33

 

타겟 넘버와 X를 비교하였을 때,

X = 16 < 타겟 넘버 = 25

타겟 넘버인 25가 X인 16보다 더 크기 때문에 정렬된 데이터에서 25는 16보다 우측에 있다는 것이 정해진 것이다.

10

16

25

33

 

그럼 또 데이터가 반으로 줄어들 것이다.

25

33

 

X를 수정해야 할 차례이다.

현재 비교해야 할 데이터의 중간 값인 25를 X의 값으로 정한다.

25

33

 

타겟 넘버와 X를 비교하였을 때,

X = 25 == 타겟 넘버 = 25

이렇게 하여 타겟 넘버인 25를 찾게 되었다.

 

한번 더 똑같은 데이터로 다른 타겟 넘버를 찾아보겠다.

이번에 사용할 타겟 넘버는 5이다.

임의의 값 X는 처음과 같이 데이터의 중간 값인 8로 시작한다.

1

5

6

8

10

16

25

33

 

이제, 타겟 넘버와 X를 비교하였을 떄,

X = 8 > 타겟 넘버 = 5

타겟 넘버인 5가 X인 8보다 더 작기 때문에 정렬된 데이터에서 5는 8보다 좌측에 있다는 것이 정해진 것이다.

1

5

6

8

10

16

25

33

 

그럼 비교해야 할 데이터가 반으로 줄어들게 될 것이다.

1

5

6

 

이제 X를 수정 할 차례이다.

현재 비교해야 할 데이터의 중간 값인 5를 X로 정한다.

1

5

6

 

타겟 넘버와 X를 비교했을 때,

 X = 5 == 타겟 넘버 = 5

이렇게 하여 타겟 넘버인 5를 찾게 되었다.

 

이진 탐색 C언어 예제 코드

위의 이진 탐색 예시를 코드로 표현한 것이다.

BinarySearch.c

#include <stdio.h>

int main() {
	int array[8] = {1, 5, 6, 8, 10, 16, 25, 33};
	int targetNum = 25;
	int low,high,mid;
	
	low = 0;
	high = sizeof(array)/sizeof(int) - 1;
	while(low <= high)
	{
		mid = (low + high) / 2;
		if(targetNum == array[mid])
		{
			printf("Target index : %d", mid);
			return 0;
		}
		else if(targetNum > array[mid])
			low = mid + 1;
		else if(targetNum < array[mid])
			high = mid - 1;
	}
	return 0;
}

 

low = 0; // 데이터의 첫번째 인덱스 
high = sizeof(array)/sizeof(int) - 1; // 데이터의 마지막 인덱스

low의 값과 high의 값은 중간 값을 찾기 위해서 필요한 값이다.

배열의 첫번째 인덱스는 0으로 시작하기 때문에 low의 값은 0으로 주고,

배열의 마지막 인덱스는 C의 경우는 배열의 요소 개수에서 하나를 뺀 값으로 주어졌다.

그 이유는 마찬가지로 배열은 0부터 시작하기 때문에 마지막 인덱스는 전체 요소의 개수 - 1 이 되기 때문이다.

while(low <= high) // low가 high 보다 커지면 타겟 넘버가 데이터에 없다
{
	mid = (low + high) / 2; // 중간 값 X를 만들어 내는 방법
	if(targetNum == array[mid]) // X와 타겟 넘버가 일치할 시
	{
		printf("Target index : %d", mid);
		return 0;
	}
	else if(targetNum > array[mid]) // 타겟 넘버가 X보다 클 때
		low = mid + 1;
	else if(targetNum < array[mid]) // 타겟 넘버가 X보다 작을 때
		high = mid - 1;
}

반복문의 조건으로는 low<=high 를 주었는데, 

low의 값이 high의 값 보다 커지게 되면, 데이터에서 타겟 넘버가 없기 때문이다.

mid는 중간 값 X를 찾기 위해 사용되는 변수이다. 중간 값을 찾는 방법으로는 '최소 인덱스와 최대 인덱스를 더한 값을 나누었을 때의 몫'을 사용했다.

조건문에서는 타겟 넘버와 X 값이 일치할 때는 값을 출력,

타겟 넘버가 X보다 클 때는 low의 값을 mid + 1 값으로 바꾸게 된다.

그 이유는, 비교할 필요가 없는 인덱스는 제외하고 비교해야 할 인덱스들 중에서 중간 값을 찾아야 하기 때문이다.

ex) X가 8이고 타겟 넘버가 25일 경우

1[0] 최솟값

5[1]

6[2]

8[3]

10[4]

16[5]

25[6]

33[7] 최댓값

 

위의 코드 상에서 mid 값은 8의 인덱스인 3인데, 타겟 넘버 25와 비교했을 떄

25가 8보다 크다는 것은 결정되었기에 8도 더이상 비교할 필요가 없는 대상이 된 것이다.

그렇기에 'mid 값 + 1' 을 하여서 인덱스가 3 이하인 값은 비교 대상에서 제외시켜 버리는 것이다.

1[0]

5[1]

6[2]

8[3]

10[4] 최솟값

16[5]

25[6]

33[7] 최댓값

 

마찬가지인 이유로 타겟 넘버가 X보다 작을 때에는 high 값을 mid - 1로 바꾸는 것이다.

ex) X가 8이고 타겟 넘버가 5인 경우

1[0] 최솟값

5[1]

6[2]

8[3]

10[4]

16[5]

25[6]

33[7] 최댓값

 

위에서 설명했듯이 mid 값은 3이고 타겟 넘버는 5여서 

인덱스가 3인 요소 8은 더이상 비교대상이 아니게 된다.

1[0] 최솟값

5[1]

6[2] 최댓값

8[3]

10[4]

16[5]

25[6]

33[7]

 

이진 탐색을 함수로 구현하면 아래와 같다.

BinarySearchFunction.c

#include <stdio.h>

int BinarySearch(int array[], int arraySize ,int targetNum);
int main() {
	int array[8] = {1, 5, 6, 8, 10, 16, 25, 33};
	int arraySize = sizeof(array)/sizeof(int) - 1;
	int targetNum = 25;
	
	printf("%d",array[BinarySearch(array, arraySize ,targetNum)]);
}

int BinarySearch(int array[], int arraySize ,int targetNum)
{
	int low,high,mid;
	
	low = 0;
	high = arraySize;
	while(low <= high)
	{
		mid = (low + high) / 2;
		if(targetNum == array[mid])
		{
			return mid;
		}
		else if(targetNum > array[mid])
			low = mid + 1;
		else if(targetNum < array[mid])
			high = mid - 1;
	}
	return -1;
}