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

현재 차근차근 해보자는 생각에 기초적인 부분을 공부하고 있다. 좀 더 구체적인 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 해보겠다.

틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다.

---

📌 개념

이진 탐색(Binary Search)은 배열에서 데이터를 찾는 알고리즘이다. 전에 공부했던 선형 탐색과 달리 데이터가 정렬된 경우에만 적용할 수 있다. 찾으려는 데이터와 배열의 정중앙의 데이터를 비교하면 중앙 기준으로 왼쪽에 있는지 오른쪽에 있는지 알 수 있다. 따라서 한 번 비교하여 검색해야 할 범위를 절반으로 줄일 수 있다. 데이터를 찾거나 데이터가 없다는 것이 확실해질 때까지 이 방법을 반복한다.

 

예시를 살펴보겠다.

이진 탐색

1부터 9까지 정렬된 배열이 있다.

 

이진 탐색

6을 찾는다고 가정해보자

 

이진 탐색

해당 수열에서 중앙에 있는 숫자는 '5'다. 그래서 5와 6을 비교를 한다.

 

이진 탐색

5 < 6 이기 때문에 5 이하의 숫자는 후보에서 제외시킨다.

 

이진 탐색

남은 배열에서 중앙에 있는 숫자를 살펴보면 이번엔 '7'이다.

 

이진 탐색

마찬가지로 6과 7을 비교하면 6 < 7 이기 떄문에 7 이상의 숫자는 후보에서 제외 된다.

 

이진 탐색

이제 남은 숫는 1개이다. 탐색을 종료하고 숫자를 비교하면 6 == 6 이라서 해당 배열에는 찾는 숫자인 '6'이 존재했다는 걸 알 수 있다.

---

⏱️ 시간복잡도

이진 탐색은 배열이 정렬된 것을 이용하여 탐색 범위를 매번 절반씩 줄여 나간다.

n개 있던 데이터를 절반씩 줄이는 조작을 log₂ n번 반복하면, 데이터는 1개가 된다. 즉, 이진 탐색에서는 배열의 정중앙에 있는 수와 비교하여 탐색 범위를 절반으로 줄이는 작업을 log₂ n회 반복하면 데이터를 찾을 수 있다. 따라서 계산 시간은 O(log n)이다.

 

📌 추가 내용

이진 탐색의 계산 시간 O(log n)은 선형 탐색 O(n)에 비해 지수적으로 빠르다.

하지만 이진 탐색을 사용하려면 항상 데이터가 정렬되어 있어야 하기 때문에, 정렬을 유지하기 위한 계산 비용이 발생한다.

 

반대로 선형 탐색은 배열이 뒤죽박죽 섞여있어도 무방하다.

 

어떤 탐색을 사용할지는 탐색과 추가 중 어떤 작업을 더 빈번하게 수행하는지를 고려하여 결정하면 된다.

 

---

참고 자료

그림으로 이해하는 알고리즘 : 이시다 모리테루, 미야자키 슈이츠