개념
이진 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 찾는 데 사용되는 탐색 알고리즘입니다. 이 알고리즘은 배열을 반으로 나누어 탐색 범위를 좁혀나가는 방식으로 동작합니다. 이진 탐색은 매 단계마다 탐색 범위를 반으로 줄이기 때문에 효율적인 탐색 방법 중 하나로 알려져 있습니다.
작동 방식
- 주어진 배열을 정렬합니다. 이진 탐색은 정렬된 배열에서만 동작합니다.
- 탐색 범위를 배열의 처음과 끝으로 초기화합니다.
- 탐색 범위의 중간 위치를 찾습니다. 이를 중간 인덱스라고 합니다.
- 중간 인덱스의 값과 찾고자 하는 값을 비교합니다.
- 만약 중간 값이 찾고자 하는 값과 일치하면, 탐색을 종료하고 해당 인덱스를 반환합니다.
- 중간 값이 찾고자 하는 값보다 작으면, 탐색 범위를 중간 인덱스 다음부터 끝까지로 업데이트합니다.
- 중간 값이 찾고자 하는 값보다 크면, 탐색 범위를 처음부터 중간 인덱스 이전까지로 업데이트합니다.
- 새로운 탐색 범위에서 다시 중간 인덱스를 찾고, 이 과정을 반복합니다.
- 탐색 범위가 더 이상 줄어들지 않거나 원하는 값을 찾을 때까지 위의 과정을 반복합니다.
이진 탐색은 배열의 크기에 대해 로그 시간 복잡도 O(log n)를 가지므로 매우 효율적입니다. 그러나 배열이 정렬되어 있어야 하고, 데이터의 삽입과 삭제가 빈번하게 일어나는 경우에는 이진 탐색이 적합하지 않을 수 있습니다.
예시
예시를 위해 정렬된 배열이 [1, 3, 5, 7, 9, 11, 13]이라고 가정해 보겠습니다.
초기 상태:
- 탐색할 배열: [1, 3, 5, 7, 9, 11, 13]
- 탐색할 값: 7
- 탐색 범위: 전체 배열
첫 번째 비교:
- 중간 인덱스: 3 (배열의 길이를 반으로 나눈 값)
- 중간 값: 7 (배열의 중간 인덱스에 해당하는 값)
7과 7을 비교하여 찾고자 하는 값과 일치하므로 탐색을 종료하고 인덱스 3를 반환합니다.이진 탐색은 배열을 반으로 나누고 중간 값을 비교하여 탐색 범위를 줄이는 과정을 반복하며 값을 찾습니다. 만약 중간 값이 찾고자 하는 값보다 작으면 왼쪽 절반을 버리고, 중간 값이 찾고자 하는 값보다 크면 오른쪽 절반을 버리는 방식으로 탐색 범위를 조정합니다. 이 과정을 반복하여 찾고자 하는 값을 찾거나 탐색 범위가 없어질 때까지 진행합니다.
이진 탐색은 탐색할 배열이 정렬되어 있어야만 사용할 수 있는 알고리즘이며, 탐색 속도가 매우 빠르기 때문에 대용량의 데이터에서 효과적으로 사용됩니다.
