이진 탐색 알고리즘이란?

오늘은 탐색 알고리즘 중 빠른 탐색 속도를 가진 알고리즘 중 하나인 이진 탐색에 대해 알아보려고 한다

참고로 이진 탐색은 이름에서 알 수 있듯이 리스트를 항상 두 부분으로 나눠서 탐색해서 이진 탐색이라고 이름이 붙여졌다

이진 탐색이란?

이진 탐색 알고리즘은 정렬된 리스트에서 특정 값을 효율적으로 찾기 위해 탐색 범위를 반으로 줄여나가며 리스트의 중간 요소를 선택하고 목표 값과 비교하여 목표 값의 위치를 정확히 판단하는 방식으로

원하는 값을 찾는 특징을 가지고 있는 알고리즘이다 이러한 방식을 사용하기 때문에 이진 탐색 알고리즘은 로그 시간 복잡도인 O(log N)으로 매우 빠른 탐색 성능을 가졌다

이진 탐색의 작동 방식

이러한 선형 탐색은 다음과 같은 방식으로 작동한다

1. 정렬된 배열의 중앙에 있는 원소를 선택한다
2. 중앙 원소와 찾고자 하는 목표 값을 비교한다
3. 만약 목표 값이 중앙 원소보다 크면 오른쪽, 작다면 왼쪽 하위 리스트에서 탐색을 계속한다
4. 이 과정을 목표 값이 발견될 때까지 또는 탐색 영역이 없어질 때까지 반복한다

글로만 보면 잘 이해가 안될 수 있으니 예시를 들어 설명하자 3을 찾을 때 이진 탐색 알고리즘을 사용한다고 했을 때

주어진 리스트: [1, 3, 5, 7, 9, 11, 13, 15]

첫 번째 진행:

[1, 3, 5, 7, 9, 11, 13, 15]

가운데 값인 7을 선택해서 3과 비교 -> 3보다 크니 왼쪽 리스트 [1, 3, 5]를 선택 

두 번째 진행:

[1, 3, 5]

가운데 값인 3을 선택해서 3과 비교 -> 3과 같다

이와 같은 과정을 통해서 이진 탐색은 주어진 값을 찾게 된다

이진 탐색의 장단점

마지막으로 이진 탐색 알고리즘에 장단점을 알아보자

장점:

1. 시간 복잡도가 O(log N)로 매우 빠르다
2. 추가적인 메모리를 사용하지 않는다

단점:

1. 배열이 정렬되어 있어야만 사용할 수 있다
2. 동일한 값이 여러 개 있을 경우 해당 값의 정확한 위치를 알기 어렵다