개요

---

Binary Search(이진 탐색)은 업 앤 다운과 같은 게임에서 숫자를 절반씩 줄여 나가는 과정과 본질적으로 동일합니다.
Sorting이 되어 있는 Array에서 element가 존재하는지 확인하고자 할 때, 가운데에 있는 element($e_m$)와 내가 찾고자 하는 값($v$)을 비교하면 세 가지 경우의 수가 나올 수 있는데, 이를 바탕으로 주목하려는(잠재적으로 내가 찾고자 하는 값이 있을 가능성이 있는) Index의 범위를 절반씩 줄여나가는 개념입니다.

Descending Order(내림차순)는 Ascending Order(오름차순)의 역순이므로 이 글에서는 Ascending Order라고 가정한 후 설명할 예정입니다.

과정

---

1. $e_m > v$

   $e_m$이 $v$ 보다 크므로 $e_m$보다 큰 값들을 가지고 있는 $e_m$ 이후의 원소들은 어떠한 경우이더라도 $v$를 포함하지 않습니다.

   그 결과 우리는 $e_m$이 $i$ 번째 Index에 존재한다고 가정한다면, 우리가 Searching 하고자 하는 List의 첫 번째 Index에서부터 $i-1$ 번째 Index까지만 고려하면 됩니다.

2. $e_m = v$

   Array 내에 해당 값이 존재하거나 혹은 해당 값을 가지고 있는 Index를 찾고자 하는 목적이었다면 더 이상 탐색할 필요가 없습니다.

   그 결과 이 값을 포함하고 있는 Array의 Index를 반환하거나, 혹은 해당 값이 Array 내에 있음을 반환하면 됩니다.

3. $e_m < v$

   $e_m$이 $v$ 보다 작으므로 $e_m$보다 작은 값들을 가지고 있는 $e_m$ 이전의 원소들은 어떠한 경우이더라도 $v$를 포함하지 않습니다.

   그 결과 우리는 $e_m$이 $i$번째 Index에 존재한다고 가정한다면, 우리가 Searching 하고자 하는 Array의 $i+1$번째 Index에서부터 마지막 Index만 고려하면 됩니다.

위에서 언급한 과정을 바탕으로 우리가 찾아보아야 하는 Array의 범위를 약 절반으로 줄일 수 있었습니다. 하지만 우리에게는 아직까지 약 절반의 Array가 남아있습니다. 이 Array들은 어떻게 해결해야 할까요?

답은 생각보다 쉽습니다. 남은 Array에 대해서 똑같은 과정을 동일하게 수행합니다. 이러한 과정을 계속해서 진행하다 보면 결국 아무런 element도 남지 않는 경우가 생깁니다. 이는 Array 내에 해당 값이 존재하지 않다는 의미이므로 존재하지 않는다고 프로그램이 반환하면 됩니다.

예시

---

아래의 정렬된 Array에서 7이 존재하는지 찾고자 하는 과정을 Binary Search Algorithm을 통해 해결해 보도록 하겠습니다.

이 Array는 0부터 시작해 6까지의 Index가 있습니다. 가장 가운데에 있는 3번 Index의 원소와 우리가 찾고자 하는 값인 7을 비교합니다.

$e_m$인 6이 $v$인 7보다 작으므로 우리는 6 이후의 원소에만 주목하면 됩니다. 이를 바탕으로 또 다시 남은 원소들에 대해 Binary Search를 수행하면 아래와 같이 원래 Array의 Index가 5인 원소와 우리가 찾고자 하는 값을 비교하는 과정을 진행하게 됩니다.

Index가 5인 원소의 값은 10입니다. 10은 7보다 작기 때문에, 우리는 10 이후에 있는 원소들을 탐색할 필요가 없게 됩니다. 남은 원소는 Index가 4인 원소만 존재하므로, Index가 4인 원소인 8과 우리가 찾고자 하는 값인 7을 비교합니다.

8과 7은 같지 않습니다. 이때 8을 제외하게 된다면, 더 이상 우리는 비교할 대상이 없습니다. 그 결과 우리는 이 Array에는 7이라는 원소가 존재하지 않음을 결론지을 수 있습니다.

Time Complexity

---

Binary Search는 1회 진행할 때마다 우리가 탐색해야 할 원소의 수가 절반으로 감소합니다. 우리가 이 Array에 우리가 찾고자 하는 값이 존재하는가?에 대한 질문에 대해 답변하기 위해 일반적으로 떠올리는 앞에서부터 하나씩 원소를 탐색하면서 찾는 방법과 대조적으로 적은 비교 만으로도 빠르게 관련이 없는 원소들을 지워 나갈 수 있다는 장점이 있습니다.

절반씩 줄여 나간다는 특성 덕분에 시간 복잡도는 $O(\log n)$입니다.

맹점

---

이렇게 완벽해 보이는 Binary Search에도 맹점은 있습니다.

바로 Array 기반의 Random Access가 가능한 자료 구조가 아닐 경우 적용이 불가능합니다.

간단히 Linked List를 생각해 볼게요. Linked List는 Linked List를 구성하는 Node가 다음 Node를 가리키는(참조하는) 구조입니다. 그렇게 될 경우 Linked List에서 가운데에 있는 원소를 $O(1)$이 걸리는 연산으로 접근하는 것은 불가능합니다. 그 결과 우리는 Binary Search가 $O(\log n)$의 Time Complexity를 가진다고 하였지만 이는 Array와 같이 Random Access가 가능한 자료 구조에서만 가능한 이야기입니다.

이런 자료 구조에서는 어차피 다른 원소에 접근하기 위해 이전 원소를 접근해야 하므로 오히려 처음 원소부터 마지막 원소까지 우리가 찾고자 하는 원소가 맞는지 확인하는 방법이 경제적이라고 이야기 할 수 있습니다.

또한 Random Access를 하기 위해서는 사전에 Array의 길이가 결정되어야 합니다. 이는 메모리 낭비 혹은 미리 할당한 길이보다 더 많은 자료가 제공된 경우 Overflow가 발생하는 문제가 존재합니다.

개선

---

이러한 문제점을 해결하기 위한 방법이 있을까요? Binary Search Tree를 바탕으로 어느정도 문제를 해결할 수 있습니다. Binary Search Tree 또한 완벽한 자료 구조는 아니지만 Binary Search 과정에서 살펴볼 수 있었던 이점을 바탕으로 자료의 개수가 정해지지 않은 자료 구조에서 상대적으로 빠른 탐색 시간을 제공합니다.

Binary Search Tree와 이에 파생된 다양한 Tree들은 다른 게시물에서 다루도록 하겠습니다.