이진 탐색 (Binary Search) (1) - 이진 탐색이란?

이진 탐색이란 데이터가 모두 정렬된 상태에서 탐색 범위를 절반씩 쪼개면서 탐색을 진행하는 알고리즘이다. 즉, 이진 탐색은 중간지점 (이하 중간점) 의 데이터를 찾고자 하는 데이터와 비교하여 탐색 범위를 좁힌다는 특징을 갖고 있다. 여기서 중간점 = (시작점 + 끝점) // 2 의 식으로 구하게 되며, 이때 // 는 버림 나눗셈 연산자로 나눗셈을 진행하고 몫의 정수 부분만 취하는 파이썬 연산자이다.

이진 탐색을 진행하는 과정을 살펴보자.

0 1 2 3 4 5 6 7 8 9

위와 같이 오름차순 정렬되어 있는 데이터가 있다고 가정하자. 여기서 우리는 3이라는 데이터가 어디에 위치해있는지를 탐색하고 싶다. 가장 먼저 시작점 = 0, 끝점 = 리스트의 마지막 인덱스 로 초기화 한다. 중간점 = (시작점 + 끝점) // 2 = (0 + 9) // 2 = 4의 값을 갖는다. 

이 때 4번째 인덱스에 해당하는 값인 4는 찾고자 하는 데이터인 3보다 큰 값을 갖는다. 이러한 경우에는 현재 중간점을 기준으로 앞의 영역을 탐색해야 하므로 끝점 = (중간점 - 1)의 값으로 변환한다. 이때 시작점은 이전 시작점을 유지한다.

끝점 = (중간점 - 1) = (4 - 1) = 3의 인덱스를 갖게 된다. 다시 중간점을 구하면 중간점 = (시작점 + 끝점) // 2 = (0 + 3) // 2 = 1의 인덱스를 갖고 해당 인덱스의 데이터는 1로 찾고자 하는 3보다 작은 값이다. 이 경우는 중간점이 찾고자 하는 데이터보다 작은 경우에 해당하고 이때는 시작점 = (중간점 + 1)의 값으로 변환한다. 마찬가지로 이때 끝점은 이전 끝점을 유지한다.

다시 중간점을 구하면 중간점 = (시작점 + 끝점) // 2 = (2 + 3) // 2 = 2이다. 중간점에 해당하는 값인 2는 3보다 작은 수 이므로 다시 한번 시작점 = (중간점 + 1)을 진행한다.

마지막으로 중간점 = (3 + 3) // 2 = 3이 되고, 3번째 인덱스의 데이터인 3은 찾고자 하는 데이터이므로 해당 중간점을 반환하면 이진 탐색을 완료하게 된다. 이러한 일련의 과정을 요약해서 정리하면 아래와 같다.

이진 탐색 (탐색 범위를 반으로 쪼개면서 탐색하는 알고리즘, 정렬되어 있을때만 사용가능)
  1. 시작점 = 0, 끝점 = 리스트의 마지막 인덱스로 초기화
  2. 중간점 = (시작점 + 끝점) // 2
  3. 중간점과 찾는 데이터를 비교하면 3가지 경우가 발생
    3-1. 중간점 = 찾는 데이터 인 경우, 해당 중간점을 반환
    3-2. 중간점 > 찾는 데이터 인 경우, 끝점 = (중간점 - 1) 로 변환
    3-3. 중간점 < 찾는 데이터 인 경우, 시작점 = (중간점 + 1)로 변환
  4. 2번, 3번 과정을 반복 

이진 탐색은 앞서 말했듯이 탐색 범위를 절반씩으로 쪼개면서 탐색을 진행하므로 퀵 정렬과 유사한 방법을 취한다. 또한 그로 인해서 탐색 속도가 매우 빠르다는 장점을 갖고 있다. 이진 탐색 알고리즘은 O(logN), N : 데이터의 개수 의 시간 복잡도 를 갖는다. 

이진 탐색을 구현하는 방법은 크게 2가지가 있다. 첫째로 재귀 함수를 통해서 구현하는 방법, 둘째로 단순하게 반복문을 통해서 구현하는 방법이다. 해당 방법들의 소스코드는 아래의 캡쳐와 같다.

재귀 함수를 통해서 구현한 이진 탐색

 

반복문을 통해 구현한 이진 탐색

---

이진 탐색의 원리는 다른 알고리즘에서도 폭넓게 사용되기 때문에 암기해두는 편이 좋다. 또한 이진 탐색은 코딩 테스트에서 탐색 범위가 큰 상황을 가정하는 문제로 자주 출제된다. 

• 탐색 범위가 2,000만을 넘어가는 경우
• 데이터 개수나 값이 1,000만 단위 이상인 경우

위의 경우와 유사할 때는 이진 탐색과 같이 O(logN)의 시간 복잡도를 갖는 알고리즘으로 문제를 해결해야 한다는 것을 기억하자.