이진 검색
- 高洛峰원래의
- 2016-12-19 16:23:491862검색
1. 이진 검색
이진 검색은 반 검색이라고도 합니다.
이진 검색 요구 사항: 선형 테이블은 순서가 지정된 목록입니다. 즉, 테이블의 노드는 키워드에 따라 정렬되고 벡터는 테이블의 저장 구조로 사용됩니다. 시퀀스 테이블은 오름차순이라고 가정할 수 있다.
2. 이진 검색의 기본 아이디어
이진 검색의 기본 아이디어는 다음과 같습니다. (R[low..high]가 현재 검색 간격이라고 가정)
(1) 먼저 간격 위치의 중간을 결정합니다:
(2) 그런 다음 확인할 k 값을 R [mid]와 비교합니다. 키: 동일하면 성공을 찾아 이 위치로 돌아갑니다. 그렇지 않으면 다음을 결정해야 합니다. 새로운 검색 범위를 찾고 2점 검색을 계속하여 찾는데, 구체적인 방법은 다음과 같습니다.
①R[mid].key>K이면 테이블의 질서가 R[mid. .n].keys는 모두 K보다 크므로 테이블 노드에 K와 동일한 키가 있는 경우 해당 노드는 mid 위치 왼쪽에 있는 하위 테이블 R[1..mid-1]에 있어야 합니다. 새로운 검색 간격은 왼쪽 하위 테이블 R[1..mid-1]입니다.
②마찬가지로 R[mid].key
int BinSearch(SeqList R, KeyType K)
{ //순서 있는 리스트 R[1..n]에서 이진 검색을 수행하고, 다음과 같은 경우 노드를 반환합니다. 위치 성공, 실패 시 0 반환
int low=1, high=n, mid; //현재 검색 간격의 상한과 하한의 초기값 설정
while(low<=high){ / /현재 검색 간격 R [low..high] non-empty
mid=(low+high)/2;
if(R[mid].key==K) return mid; 성공하고 반환
if(R [MID] .kdy & gt; k)
High = mid-1; //
Else
참조 Low = MID+1 in R [Low.. Mid -]; // R 검색
에서 계속 [mid+1..high] }
~ 재귀 프로그램을 제공하는 것은 쉽습니다. [연습 참조]
4. 실행 프로세스 이진 검색 알고리즘
알고리즘의 입력 인스턴스에서 키워드의 순서가
이라고 가정합니다. 찾을 키워드 K는 각각 21과 85입니다. 특정 검색 프로세스 [애니메이션 데모 참조]
5. 이진 검색 결정 트리
이진 검색 프로세스는 이진 트리로 설명할 수 있습니다. 현재 검색 간격의 중간에 있는 노드를 루트로 사용합니다. , 왼쪽 하위 테이블 및 오른쪽 하위 테이블 하위 테이블의 노드는 각각 루트의 왼쪽 하위 트리 및 오른쪽 하위 트리 역할을 합니다. 결과로 나온 이진 트리를 이진 검색을 설명하는 의사결정 트리(Decision Tree) 또는 비교 트리(Comparison Tree)라고 합니다.
의사결정 트리의 모양은 테이블 노드 수 n에만 관련되며 입력 인스턴스의 R[1..n].keys 값과는 아무런 관련이 없습니다.
[예시] 11개의 노드로 구성된 정렬된 목록은 아래 그림과 같은 의사결정 트리로 표현할 수 있습니다.
(1) 이진 탐색 결정 트리의 구성
① 원 노드는 트리의 내부 노드이다. 트리에서 원 노드 내부의 숫자는 순서가 지정된 목록에서 노드의 위치를 나타냅니다.
③트리의 노드 i를 왼쪽(오른쪽) 자식에 연결하는 왼쪽(오른쪽) 가지의 "<", "(", ">", ")" 표시는 다음을 나타냅니다. 검색 K (2) 이진 탐색 결정 트리 탐색 (3) 이진 검색의 평균 검색 길이 이진 검색은 순차 저장 구조에만 적용됩니다. 테이블의 순서를 유지하기 위해서는 순차구조에서는 삽입과 삭제 시 많은 수의 노드를 이동시켜야 한다. 따라서 이진 검색은 일단 생성되면 거의 변경되지 않고 자주 검색해야 하는 선형 테이블에 특히 적합합니다. #include void TwoInsertSort(int array[],int n) int rcmp( const int *a, const int *b) //라이브러리 함수 bsearch는 이진법을 사용하여 정렬된 배열에서 특정 숫자를 찾고 해당 숫자의 주소를 반환합니다 a = (int *)bsearch(&b, numarray, sizeof(numarray)/sizeof(numarray[0]), sizeof(int),rcmp); 이진 검색에 관한 더 많은 글은 PHP 중국어 홈페이지를 주목해주세요!
이진 탐색은 주어진 값 K를 이진 탐색 결정 트리의 루트 노드에 있는 키워드와 비교하는 것입니다. 같으면 성공. 그렇지 않고 루트 노드의 키보다 작으면 왼쪽 하위 트리에서 검색합니다. 루트 노드의 키보다 크면 오른쪽 하위 트리에서 검색합니다.
[예] 11개의 노드가 있는 테이블의 경우 검색되는 노드가 테이블의 6번째 노드인 경우 검색되는 노드가 테이블의 3번째 또는 9번째 노드인 경우 1개의 비교만 필요하며, 2개의 비교가 필요합니다. 1번째, 4번째, 7번째, 10번째 노드를 찾으려면 세 번의 비교가 필요하고, 2번째, 5번째, 8번째, 11번째 노드를 찾으려면 네 번의 비교가 필요합니다.
성공적인 이진 검색 프로세스는 의사결정 트리의 루트에서 검사 중인 노드까지 정확히 경로를 취하며, 비교된 키워드의 수는 정확히 해당 노드의 레벨 수와 일치함을 알 수 있습니다. 나무. 검색에 실패할 경우 비교 과정은 의사결정 트리의 루트부터 외부 노드까지의 경로를 거치게 되며, 필요한 키워드 비교 횟수는 해당 경로에 있는 내부 노드의 총 개수입니다.
【예】 조회할 테이블의 키워드 순서는 (05, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92)입니다. K=85인 레코드를 찾으려면 , 프로세스 내부 노드는 6, 9, 10이며 최종적으로 사각형 노드 "9-10"에 도달하고 비교 횟수는 3입니다.
사실 정사각형 노드에서 "i-i+1"의 의미는 찾고자 하는 값 K가 R[i].key와 R[i+1].key 사이에 있다는 뜻입니다. R[i] .key
내부 노드의 총 개수가 n=2h-1이라고 가정하면, 판단 트리는 깊이 h=lg( n+1) (깊이 h에는 외부 노드가 포함되지 않음) 트리의 k번째 수준에 있는 노드 수는 2k-1이고, 이를 찾는 데 필요한 비교 횟수는 k입니다. 따라서 등확률 가정 하에서 이진 검색이 성공할 때의 평균 검색 길이는 다음과 같습니다. 최악의 경우 성공적인 비교 횟수는 결정 트리의 깊이를 초과하지 않습니다. 즉,
이진 검색의 최악의 성능과 평균 성능은 꽤 가깝습니다.
6. 이진 검색의 장점과 단점
검색이 거의 필요하지 않고 종종 수정이 필요한 선형 테이블의 경우 연결 목록을 저장 구조로 사용하여 순차 검색을 수행할 수 있습니다. 연결된 목록에서는 이진 검색을 구현할 수 없습니다.
이중 정렬
{
int left,right,num;
int middle,j,i;
for(i = 1;i < n;i++)
{
left = 0;/ / 준비하세요
middle = ( left + right ) / 2; // 정렬된 중간 위치를 가리킵니다
if( num < array[middle] )// 삽입할 요소는 왼쪽 간격에 있어야 합니다
right = middle-1;
else else // 삽입할 요소는 오른쪽 간격에 있어야 합니다.
left = middle+1
}
for( j = i-1;j >= left;j-- )//R[i]보다 큰 정렬 코드가 있는 레코드로 뒤로 이동
array[j+1] = array[j];
{
return (*a-*b);
}
void main()
{
int array[50];
int i;
printf("원래 배열은 :n");
for( i=0; i {
array[i] = 50-i;
printf("array[%d]:%dn", i, array[i]);
}
TwoInsertSort(array,sizeof (array)/sizeof(int));//이진 정렬
printf("nAfter sorted :n");
for( i=0; i printf("array [ %d]:%dn", i, array[i]);
}