[알고리즘] 이진 탐색(Binary Search)

 

 

INDEX

1. 정의

2. 방법

3. 소스 구현

4. 장점

5. 단점

1. 정의

▶ 오름차순으로 정렬된 1차원 배열에서 특정한 값을 찾아내는 알고리즘

 

반드시 오름차순으로 정렬된 배열에서만 사용 가능하다. 왜냐하면 찾으려는 숫자가 n일 때 현재의 위치가 n보다 작을 때 n은 반드시 현재의 위치보다 뒤에 있음을 기본으로 깔고 있기 때문이다. 

 

또한 이진 탐색을 사용하는 목적은 크게 두 가지가 있다. 

1. 찾고자 하는 원소가 배열에 있는지에 대한 존재 여부.
2. 찾고자 하는 원소가 배열에 있다는 것을 확실히 알고 있지만 위치 정보를 알고 싶을 때.

 

2. 방법

오름차순 배열과 찾고자 하는 값(6)이 있다고 가정하자.

{ 1, 2, 3, 4, 5, 6, 7 }

1. 우선 배열의 중간에 있는 값(4)을 입력한다.
2. 현재 위치(4)와 찾고자 하는 값(6)을 비교한다.
3. 찾고자 하는 값이 더 크므로 현재 위치를 기준으로 현재 위치를 제외한 배열로 다시 탐색을 진행한다.                                                       { 5, 6, 7 }
4. 중간에 있는 값(6)을 입력한다.
5. 찾고자 하는 값과 일치하므로 탐색 종료

물론 배열에 찾고자 하는 값이 존재한다면 종료하면 되지만 만약에 찾고자 하는 값이 없다면 어떻게 될까?

 

예를 들어 6을 찾고 있는데 6이 배열에 없는 상태라고 가정해 보자

{ 1, 2, 3, 4, 5, 7 }

이번에는 배열의 길이가 짝수이므로 한가운데 요소를 정확히 찾을 수가 없다! 따라서 중간 요소를 선택하기 위해서 우리는 주로 { 0(1의 인덱스)+5(7의 인덱스) } / 2 = 2(2.5의 내림)의 계산을 거쳐 결국 3을 중간 값으로 잡는다. 

 

따라서 우리가 관찰해야 하는 배열은 아래와 같이 변한다.

{ 1, 2, 3, 4, 5, 7 } -> (3 선택)

        { 3, 4, 5, 7 } -> (4 선택)

                { 5, 7 } -> (5 선택)

                    { 7 }

이렇게 마지막 원소 7이 남게 되었는데 6과 다르기 때문에 6은 애초에 배열 안에 존재하지 않았던 것이다.

 

다른 예시로 1~10이 저장된 배열에서 4를 찾아보자.

1	2	3	4	5	6	7	8	9	10
1	2	3	4
		3	4
			4

 

3. 소스 구현

원리를 알아도 코드 구현을 못하면 무용지물! 반목문을 이용한 방법과 재귀함수를 이용한 방법을 각각 python과 c로 짜보자

 

먼저 위에서 언급한 1번 목적으로 작동하는 이진 탐색 함수를 만들어보자.

<반복문(python)>

def binary_search(arr, target):
    start, end = 0, len(arr) - 1
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == target:
            return 1
        elif arr[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return 0

찾고자 하는 target이 배열에 없을 때는 다음과 같은 현상이 생긴다.

• start와 end가 같아진다.
• mid를 계산하고 나서 반드시 elif 또는 else로 빠지게 된다.
• elif로 빠지면 end가 1 감소된 상태이므로 start> end 이므로 반복문 탈출, else로 빠지면 start가 1 증가된 상태이므로 start>end 이므로 반복문 탈출

<재귀(python)>

def binary_search(arr, target, start, end):
    if start > end:
        return 0

    mid = (start + end) // 2
    if arr[mid] == target:
        return 1
    elif arr[mid] > target:
        return binary_search(arr, target, start, mid - 1)
    else:
        return binary_search(arr, target, mid + 1, end)

<반복문(C)>

int binary_search(int arr[], int target)
{
	int start=0;
	int end=sizeof(arr)/4-1;
	int mid;
	while(start<=end)
	{
		mid=(start+end)/2;
		if (arr[mid]==target)
			return 1;
		else if(arr[mid]>target)
			end=mid-1;
		else
			start=mid+1;	
	}
	return 0;
}

end 구하는 법 : arr는 int 형으로 선언되었기 때문에 배열 공간 한 개당 4바이트의 크기를 차지함. 따라서 arr의 크기는 (4*선언된 크기) / 4이다. 마지막으로 인덱싱을 위해 1을 빼줌으로써 arr의 마지막 인덱스를 알아낸다.

<재귀(C)>

int binary_search(int arr[], int target, int start, int end)
{
	if(start>end)
		return 0;
	int mid=(start+end)/2;
	if (arr[mid]==target)
		return 1;
	else if(arr[mid]>target)
		return binary_search(arr, target, start, mid-1);
	else
		return binary_search(arr, target, mid+1, end);
}

전체적인 코드에서 mid-1, mid+1와 같이 이동하는 이유는 mid를 검사했음에도 mid가 target이 아니면 mid를 재검사할 인덱에 포함시킬 필요가 없기 때문이다.

 

이제부터는 2번 목적의 함수를 만들어보자.

<반복문(python)>

def binary_search(arr, target):
    start, end = 0, len(arr) - 1
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            end = mid - 1
        else:
            start = mid + 1

<재귀(python)>

def binary_search(arr, target, start, end):
    mid = (start + end) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search(arr, target, start, mid - 1)
    else:
        return binary_search(arr, target, mid + 1, end)

<반복문(C)>

int binary_search(int arr[], int target)
{
	int start=0;
	int end=sizeof(arr)/4-1;
	int mid;
	while(start<=end)
	{
		mid=(start+end)/2;
		if (arr[mid]==target)
			return mid;
		else if(arr[mid]>target)
			end=mid-1;
		else
			start=mid+1;	
	}
}

<반복문(C)>

int binary_search(int arr[], int target, int start, int end)
{
	int mid=(start+end)/2;
	if (arr[mid]==target)
		return mid;
	else if(arr[mid]>target)
		return binary_search(arr, target, start, mid-1);
	else
		return binary_search(arr, target, mid+1, end);
}

 

4. 장점

1. 검색이 반복될 때마다 목표를 찾을 확률이 2배 가까이 증가한다. 예를 들어 원소가 100개인 정렬된 배열에 대해 이진 탐색을 진행하면 진행 횟수당 경우의 수는 아래와 같이 변한다.

100 → 50 or 49 → 25 or 24 → 12 or 11 → 6 or 5 → 3 or 2 → 1 or 1 → 찾았다! or 배열 안에 있다.없다!

 

2. 처음부터 그다음 요소로 차근차근 하나씩 찾아보는 방법인 선형 검색이 O(N)의 시간 복잡도를 가지지만 정렬되어 있는 배열에 대해서는 O(logN)의 획기적인 시간 복잡도를 갖는다.

5. 단점

1. 정렬을 해야 한다. 정렬이라는 행위 자체가 대형 자료 구조에 대해서는 아킬레스건일 수밖에 없다. 심지어 정렬과 이진 탐색 과정을 함께 묶어서 시간 복잡도를 구해보면 O(NlogN)이 나오게 되고 이것은 선형 검색(O(N))보다 오래 걸린다는 뜻이다. 물론 검색을 여러 번 진행해야 하는 상황에서는 정렬(힙 정렬, 병합 정렬, 퀵 정렬 → O(NlogN))을 일단 하고 탐색(logN)을 계속 사용하는 것이 유리하기 때문에 이진 탐색이 훨씬 유리하다. 

여기서 의문이 든다. 기수 정렬과 카운팅(계수) 정렬은 시간 복잡도가 O(N)이어서 힘, 병합, 퀵을 대신하면 정렬+이진 탐색을 O(N)에 끝낼 수 있는데 왜 O(NlogN)으로 알려져 있을까? 그 이유는 정렬해야 하는 배열의 크기가 많이 커지면 메모리 요구량이 많아지기 때문에 이진 탐색에 대해서는 비교 기반 정렬이 더 현명하기 때문이다.

 

2. 자료형이 일정해야 한다. 자료형이 일정하지 않으면 애초에 정렬이 불가하기 때문이다.

 

3. 재귀 사용에 제약이 있다. 반복문의 공간 복잡도는 O(1)인 반면 재귀를 사용할 시 O(logN)으로 늘어난다. 그 이유는 스택 공간(stack space)의 사용에 있다. 재귀 함수를 호출할 때마다 현재 실행 중인 상태(로컬 변수와 반환 주소)를 저장하고 새로운 함수(결국은 자기 자신이지만...)를 호출하기 위한 공간으로 메모리 스택을 사용한다. 재귀가 반복되면 호출 스택에 스택 프레임이 쌓이게 되고 이게 심해질 경우 결국 stack overflow를 야기하게 된다. 즉 데이터 세트가 많이 프로그램의 비정상적인 종료를 야기할 수 있다. 

 

4. 정적 데이터 구조에 사용이 국한된다. 연결 리스트와 같이 특정 값에 대한 무작위 접근을 허용하지 않는 자료구조에서는 사용이 힘들다. 그렇다고 아예 불가능한 것은 아니다. 연결 리스트를 먼저 정렬하거나 애초에 정렬된 상태로 들어간 연결 리스트에 한해서 이진 탐색을 사용할 수 있다.