EXAMPLE을 사용한 이진 검색 알고리즘

이진 검색을 배우기 전에 다음을 알아봅시다.

검색이란 무엇입니까?

검색은 사용자가 데이터베이스 내에 보관된 문서, 파일, 미디어 또는 기타 모든 유형의 데이터를 찾을 수 있게 해주는 유틸리티입니다. 검색은 기준을 기록과 일치시키고 이를 사용자에게 표시하는 간단한 원리에 따라 작동합니다. 이런 식으로 가장 기본적인 검색 기능이 작동합니다.

이진 검색이란 무엇입니까?

이진 검색은 정렬된 항목 목록에서 데이터를 찾아 가져오는 고급 유형의 검색 알고리즘입니다. 핵심 작업 원리는 목록의 데이터를 절반으로 나누어 필요한 값을 찾아 검색 결과에서 사용자에게 표시하는 것입니다. 이진 검색은 일반적으로 반간격 탐색 또는 로그 검색.

이진 검색은 어떻게 작동하나요?

이진 검색은 다음과 같은 방식으로 작동합니다.

• 검색 프로세스는 정렬된 데이터 배열의 중간 요소를 찾는 것으로 시작됩니다.
• 그 후 키 값은 요소와 비교됩니다.
• 키 값이 중간 요소보다 작을 경우 상위 값을 중간 요소까지 분석하여 비교 매칭하는 검색입니다.
• 키 값이 중간 요소보다 큰 경우 검색은 낮은 값을 중간 요소로 분석하여 비교 및 ​​매칭을 수행합니다.

예제 이진 검색

사전의 예를 살펴보겠습니다. 특정 단어를 찾아야 하는 경우, 아무도 순차적으로 각 단어를 살펴보지 않고, 필요한 단어를 검색하기 위해 가장 가까운 단어를 무작위로 찾습니다.

위의 이미지는 다음을 보여줍니다.

1. 10자리 배열이 있고 요소 59를 찾아야 합니다.
2. 모든 요소는 0 – 9의 인덱스로 표시됩니다. 이제 배열의 중간이 계산됩니다. 그렇게 하려면 지수의 왼쪽과 가장 오른쪽 값을 가져와서 2로 나눕니다. 결과는 4.5이지만 우리는 하한값을 사용합니다. 따라서 중간은 4이다.
3. 4가 59보다 크므로 알고리즘은 중간(24)에서 가장 낮은 경계까지 모든 요소를 ​​삭제하고 이제 배열에는 5개의 요소만 남습니다.
4. 이제 59는 45보다 크고 63보다 작습니다. 가운데는 7입니다. 따라서 오른쪽 인덱스 값은 middle – 1(6)이 되고 왼쪽 인덱스 값은 이전과 동일하게 5로 유지됩니다.
5. 이때 59 다음에 45가 온다는 것을 알 수 있습니다. 따라서 왼쪽 지수인 5도 역시 중간이 됩니다.
6. 이러한 반복은 배열이 단 하나의 요소로 줄어들거나 찾을 항목이 배열의 중간이 될 때까지 계속됩니다.

예제 2

이진 검색의 작동 방식을 이해하기 위해 다음 예를 살펴보겠습니다.

1. 2에서 20 사이의 정렬된 값 배열이 있고 18을 찾아야 합니다.
2. 하한과 상한의 평균은 (l + r) / 2 = 4입니다. 검색되는 값은 중간인 4보다 큽니다.
3. mid보다 작은 배열 값은 검색에서 제외되고, mid 값 4보다 큰 값이 검색됩니다.
4. 이는 실제 검색할 항목을 찾을 때까지 반복적인 분할 과정이다.

왜 이진 검색이 필요한가요?

다음과 같은 이유로 이진 검색은 검색 알고리즘으로 사용하기에 더 나은 선택입니다.

• 이진 검색은 데이터 크기에 관계없이 정렬된 데이터에서 효율적으로 작동합니다.
• 데이터를 순서대로 검색하여 검색하는 대신 이진 알고리즘은 데이터에 무작위로 액세스하여 필요한 요소를 찾습니다. 이렇게 하면 검색 주기가 더 짧아지고 더 정확해집니다.
• 이진 검색은 속도가 느리고 대부분 부정확한 동등 비교를 사용하는 것보다 순서 원칙을 기반으로 정렬된 데이터를 비교합니다.
• 매 검색 주기 후에 알고리즘은 배열의 크기를 절반으로 나누므로 다음 반복에서는 배열의 나머지 절반에서만 작동합니다.

다음 튜토리얼을 배워보세요 선형 검색: Python, C++ 예시

제품 개요

• 검색은 사용자가 문서, 파일 및 기타 유형의 데이터를 검색할 수 있는 유틸리티입니다. 이진 검색은 정렬된 항목 목록에서 데이터를 찾아 가져오는 고급 유형의 검색 알고리즘입니다.
• 이진 검색은 일반적으로 반구간 검색 또는 로그 검색으로 알려져 있습니다.
• 필요한 요소를 찾을 때마다 반복할 때마다 배열을 절반으로 나누어 작동합니다.
• The 바이너리 알고리즘 왼쪽과 가장 오른쪽 인덱스 값의 합을 2로 나누어 배열의 중앙을 가져옵니다. 이제 알고리즘은 찾을 요소에 따라 배열 중앙에서 요소의 하한 또는 상한을 삭제합니다.
• 알고리즘은 데이터에 무작위로 액세스하여 필요한 요소를 찾습니다. 이렇게 하면 검색 주기가 더 짧아지고 더 정확해집니다.
• 이진 검색은 느리고 부정확한 동등 비교를 사용하는 대신 순서 원칙을 기반으로 정렬된 데이터를 비교합니다.
• 정렬되지 않은 데이터에는 이진 검색이 적합하지 않습니다.