#4. 이진 탐색 알고리즘 구현

이진 탐색 알고리즘

기본적으로 이차원으로 정렬된 배열에서 탐색하는 알고리즘이다.

순차 탐색 알고리즘보다 좋은 성능을 보이지만 배열이 정렬되어 있어야 한다는 제약이 있다.

이때 정렬은 반드시 오름차순/내림차순 이어야 한다 가 아니라 정해진 기준이 있으면 상관없다.

 

이러한 배열이 있다고 할 때 3 이라는 값을 찾는 알고리즘을 설계한다고 해보자.

 

이진 탐색 알고리즘의 기본 골격은 다음과 같다.

1. 처음 인덱스 + 끝 인덱스 값을 더한다

2. 그 값을 2로 나눈다.

3. 해당 결과값을 인덱스로 하여 배열의 값을 탐색한다.

 

이 골격을 가지고 순서를 다시 생각해본다면

1. 처음 인덱스 : 0 / 끝 인덱스 : 8 => 8

2. 8 / 2 = 4

3. arr[4] = 9

의 과정을 거치게 된다.

 

만약 여기서 arr[4] 가 우리가 찾는 값이라면 이대로 종료할 수 있겠지만, 문제는 그렇지 않을 경우에서 생긴다.

2번의 과정에서 /2 의 계산을 거친 만큼, 우리가 탐색한 값은 배열의 중간이다.

여기서 이 값을 기준으로 왼쪽과 오른쪽으로 나뉘는데 어디를 탐색할지 결정해야 한다

 

이때 결정의 기준은 처음 언급한 제약, '정해진 기준'에서 나온다.

간단하게 오름차순이면 왼쪽, 내림차순이면 오른쪽 으로 볼 수 있는 것이다.

예시로 든 배열은 오름차순 정렬이므로 왼쪽을 탐색한다.

 

이 과정까지 지나고 나면 우리가 탐색해야 하는 데이터가 총 9개에서 4개로 줄어든 모습을 볼 수 있다.

다시 기본 골격을 반복하면

1. 첫 인덱스 : 0 / 끝 인덱스 : 3 => 3

2. 3 / 2 = 1 (이 때, 나머지는 버린다)

3. arr[1] = 2

우리가 찾는 3의 값이 아니다.

 

여기까지만 봐도 알 수 있는 것은

탐색이 진행될 때마다 탐색 대상이 절반씩 줄어든다는 것이다.

이것이 순차 탐색 알고리즘보다 좋은 성능을 보이는 이유 이다.

 

 

이진 탐색 알고리즘 구현

우리가 알 수 있는 것은

모든 탐색 과정이 인덱스의 First / Last 를 점점 줄여가면서 이루어진다는 것이다.

: First 와 Last 가 서로 만나지 않았다? ( First != Last ) = 탐색 대상이 남았다

: ... 만났다? ( First == Last ) = 탐색 대상이 하나 남았다

의 과정이다.

이 과정을 First 와 Last 가 서로 역전될 때까지 반복하는 것이다.

 

First 와 Last 의 비교를 조건으로 반복문을 시행하는데, 

First 가 Last보다 작거나 같을 때만 반복한다.

이는 아직 탐색 대상이 1개 이상이다 를 만족하며

 

만약 First 가 Last 보다 커질 경우 ( First > Last )

탐색 대상을 모두 검사했는데도 원하는 값을 찾지 못했다, 즉 해당 배열에 탐색 대상이 없다

는 뜻으로 이해하고 반복문을 종료하게 된다.

 

코드 구조

1. 탐색할 인덱스의 첫번째, 마지막 값을 받을 First, Last 변수가 존재한다.

=> 이를 통해 중앙 인덱스 값을 구해낸다.

2. 배열 중앙이 타겟값이냐 를 판별한다.

 2_1. 맞을 경우 코드 종료

3. 아닐 경우 중앙 기준 왼쪽/오른쪽 탐색을 판단

의 반복이다.

 

예시 코드

int BSearch(int ar[], int len, int target)
{
	int first = 0; //첫번째 인덱스 값
    int last = len - 1; //마지막 인덱스 값
    int center; //중간 인덱스 값
    
    while(first <= last)
    {
    	center = (first + last) / 2; //탐색 대상의 중앙
        if(target == ar[center])
        {
        	return center; //타겟이 맞을 경우 코드 종료
        }
        else //타겟이 아닐 경우
        {
        	//왜 +1, -1 을 했는지 고민해볼 문제
        	if(target < ar[center]) last = center -1;
            else first = center + 1;
        }
    }
    return -1; //타겟을 찾지 못했을 경우
}

다음과 같이 알고리즘을 작성할 수 있다.

 

주석에도 적어놨듯이, 고민해볼 문제가 하나 있다.

바로 타겟이 아닐 경우, 왜 +1, -1, 을 했냐 가 있는데 이는 사실 배열을 직접 그려서 생각해보면 쉽게 알 수 있다.

처음 예시로 들었던 배열을 다시 보면서 코드를 이해하면

center  = 4, ar[center] = 9 가 되고 당연히 찾는 값인 3이 아니다.

배열 정렬 기준은 오름차순으로 되어 있어 9의 왼쪽을 살펴야 하는데

이는 ar[0] 부터 ar[3] 까지가 될 것이다.

 

이미 탐색했던 ar[4]를 굳이 포함시킬 이유가 없는 것이다.

이것은 연산 비용 상의 문제이고 중요한 이유는 한가지 더 있다.

 

예를 들어서 찾는 값이 배열에 없는 4 이고, +1 과 -1 을 추가하지 않았다고 가정해보겠다.

탐색 과정은

1. First = 0, Last = 8, Center = 4

2. First = 0, Last = 4, Center = 2

가 될 것인데 이때 ar[Center] = 3 이므로 탐색 과정을 한번 더 실행할 것이다.

 

다시

First = 2, Last = 4, Center = 3

이 된다. 물론 ar[Center] 도 찾는 값이 아니다.

 

문제는 이때 발생한다.

현재의 조건은 target >= ar[Center] 에 해당하여 First = Center 가 될 것인데,

그러면 First = 3, Center = 3 이 되면서 First == Center 가 성립된다.

 

같은 코드 안에서 빠져나오지 못하는 무한루프에 갇히는 것이다.

실제로 코드를 돌려보면 쉽게 이해할 수 있을 것이다.

 

해서

1. 연산 비용 절감

2. 무한루프 방지

의 이유로 +1, -1 을 추가해야 한다.

 

---

내용이 상당히 길어져 시간 복잡도 계산은 다음 글에서 진행하도록 함