EXAMPLE을 사용한 이진 검색 알고리즘
사라 첸
⚡ 스마트 요약
이진 탐색 알고리즘은 정렬된 리스트에서 검색 범위를 반복적으로 절반으로 줄이고 목표 항목과 중간 항목을 비교하는 방식으로 항목을 찾습니다. 반구간 탐색 또는 로그 탐색이라고도 하는 이 알고리즘은 모든 항목을 하나씩 스캔하는 것보다 훨씬 빠릅니다.
이진 탐색을 배우기 전에 탐색이란 무엇인지부터 알아보겠습니다.
검색이란 무엇입니까?
검색은 사용자가 데이터베이스 내에 보관된 문서, 파일, 미디어 또는 기타 모든 유형의 데이터를 찾을 수 있게 해주는 유틸리티입니다. 검색은 기준을 기록과 일치시키고 이를 사용자에게 표시하는 간단한 원리에 따라 작동합니다. 이런 식으로 가장 기본적인 검색 기능이 작동합니다.
이진 검색이란 무엇입니까?
이진 검색은 정렬된 목록에서 데이터를 찾아 가져오는 고급 검색 알고리즘입니다. 핵심 작동 원리는 필요한 값을 찾아 검색 결과에 표시할 때까지 목록의 데이터를 절반씩 나누는 것입니다. 이진 검색은 일반적으로 다음과 같이 알려져 있습니다. 반간격 탐색 또는 로그 검색.
이진 검색은 어떻게 작동하나요?
이진 검색은 다음과 같은 방식으로 작동합니다.
- 검색 과정은 정렬된 데이터 배열의 중간 요소를 찾는 것으로 시작됩니다.
- 그 후, 키 값이 해당 요소와 비교됩니다.
- 키 값이 중간 요소보다 작으면 검색은 중간 요소보다 큰 값을 분석하여 비교 및 일치 여부를 확인합니다.
- 키 값이 중간 요소보다 큰 경우, 검색은 중간 요소보다 작은 값을 분석하여 비교 및 일치 여부를 확인합니다.
이진 탐색 알고리즘 (의사 코드)
이진 탐색은 간결하고 반복적인 루틴으로 작성할 수 있습니다. 이 루틴은 낮은 포인터와 높은 포인터 두 개를 유지하고, 목표값을 찾거나 범위가 비어 있을 때까지 범위를 좁혀 나갑니다.
binarySearch(array, target)
low = 0
high = length(array) - 1
while low <= high
mid = (low + high) / 2 // floor value
if array[mid] == target
return mid
else if array[mid] < target
low = mid + 1
else
high = mid - 1
return -1 // target not found
이 루틴은 성공 시 대상의 인덱스를 반환하고 값이 존재하지 않으면 -1을 반환합니다. 범위가 매 패스마다 절반으로 줄어들기 때문에 루프는 최대 log₂(n)번 실행됩니다.
예제 이진 검색
사전의 예를 살펴보겠습니다. 특정 단어를 찾아야 하는 경우, 아무도 순차적으로 각 단어를 살펴보지 않고, 필요한 단어를 검색하기 위해 가장 가까운 단어를 무작위로 찾습니다.
위의 이미지는 다음을 보여줍니다.
- 10자리 배열이 있고 요소 59를 찾아야 합니다.
- 배열의 모든 요소에는 0부터 9까지의 인덱스가 부여되어 있습니다. 이제 배열의 중간값을 계산해 보겠습니다. 이를 위해 인덱스의 가장 왼쪽과 가장 오른쪽 값을 2로 나눕니다. 결과는 4.5이지만, 내림을 하기 때문에 중간값은 4입니다.
- 알고리즘은 59가 24보다 크기 때문에 중간(4)부터 가장 낮은 경계까지의 모든 요소를 제거하고 이제 배열에는 5개의 요소만 남습니다.
- 59는 45보다 크고 63보다 작습니다. 중간값은 7입니다. 따라서 오른쪽 인덱스 값은 중간값에서 1을 뺀 값인 6이 되고, 왼쪽 인덱스 값은 이전과 같이 5로 유지됩니다.
- 이때 59 다음에 45가 온다는 것을 알 수 있습니다. 따라서 왼쪽 지수인 5도 역시 중간이 됩니다.
- 이러한 반복은 배열이 단 하나의 요소로 줄어들거나 찾을 항목이 배열의 중간이 될 때까지 계속됩니다.
예제 2
이진 검색의 작동 원리를 이해하기 위해 다음 예제를 살펴보겠습니다.
- 2에서 20 사이의 정렬된 값 배열이 있고 18을 찾아야 합니다.
- 하한값과 상한값의 평균은 (l + r) / 2 = 4입니다. 찾고자 하는 값은 중간값인 4보다 큽니다.
- 배열 값 중 중간값보다 작은 값은 검색에서 제외하고, 중간값인 4보다 큰 값들을 검색합니다.
- 이는 실제 검색할 항목을 찾을 때까지 반복적인 분할 과정이다.
왜 이진 검색이 필요한가요?
다음과 같은 이유로 이진 탐색이 검색 알고리즘으로 사용하기에 더 나은 선택입니다.
- 이진 검색은 데이터 크기에 관계없이 정렬된 데이터에서 효율적으로 작동합니다.
- 데이터를 순서대로 검색하여 검색하는 대신 이진 알고리즘은 데이터에 무작위로 액세스하여 필요한 요소를 찾습니다. 이렇게 하면 검색 주기가 더 짧아지고 더 정확해집니다.
- 이진 검색은 느리고 대부분 정확도가 떨어지는 같음 비교를 사용하는 대신 정렬된 데이터를 순서 원칙에 따라 비교합니다.
- 검색 주기가 끝날 때마다 알고리즘은 배열의 크기를 절반으로 나눕니다. 따라서 다음 반복에서는 남은 절반의 배열만 사용하게 됩니다.
다음 튜토리얼을 알아보세요 선형 검색: Python, C++ 예시.
이진 검색 vs 선형 검색
이진 검색과 선형 검색은 컬렉션에서 값을 찾는 가장 일반적인 두 가지 방법입니다. 아래 표는 두 방법의 차이점을 보여줍니다.
| 아래 | 이진 검색 | 선형 검색 |
|---|---|---|
| 데이터 요구 사항 | 정렬된 데이터가 필요합니다. | 정렬된 데이터와 정렬되지 않은 데이터 모두에서 작동합니다. |
| 방법 | 매 단계마다 검색 범위를 절반으로 줄입니다. | 각 요소를 순서대로 확인합니다. |
| 시간 복잡성 | O (로그 n) | O (N) |
| 가장 좋은 | 대규모 정렬 데이터 세트 | 규모가 작거나 정렬되지 않은 데이터 세트 |
요약하자면, 이진 검색은 정렬된 대규모 데이터에서 훨씬 빠르지만, 선형 검색은 더 간단하며 데이터가 정렬되지 않은 경우 유일한 선택지입니다.
