이진 탐색(binary search)

이진 탐색이란?

정렬되어 있는 요소들을 반씩 제외하며 찾는 알고리즘이다.

특징

1. 반드시 정렬이 되어있어야 사용이 가능하다.
2. 배열 혹은 이진 트리를 이용하여 구현가능하다.
3. O(log N)의 시간 복잡도를 가진다.

이진 탐색 트리란?

이진 탐색을 위한 이진트리로, 왼쪽 서브 트리는 루트노드의 값보다 작은 값들이 존재하며, 오른쪽 서브 트리는 루트노드의 값보다 높은 값으로 구성되어 있다.

문제점

최악의 경우 한쪽으로 편향된 트리가 될 수 있으며, 순차탐색과 똑같은 시간복잡도를 가지게 된다. 이를 해결하기 위해서는 AVL트리나 레드-블랙 트리를 사용할 수 있다.