정적 탐색 표: 순서 찾기, 반절 찾기, 블록 찾기

머리말:
       각종 선형 과 비 선형 데이터 구 조 를 제외 하고 실제 응용 에서 대량으로 사용 되 는 데이터 구조 인 검색 표 도 있다.검색 표 는 같은 유형의 데이터 요소 로 구 성 된 집합 입 니 다.
       검색 표 에서 자주 진행 되 는 작업 은 다음 과 같 습 니 다. 1. 특정한 데이터 요소 가 검색 표 에 있 는 지 찾 습 니 다.2. 특정한 데이터 요소 의 각종 속성 을 검색 합 니 다.3. 검색 표 에 데이터 요 소 를 삽입 합 니 다.4. 검색 표 에서 특정한 데이터 요 소 를 삭제 합 니 다.검색 표 에 대해 서 는 앞의 두 가지 만 '찾기' 라 고 부 르 는 동작 을 하면 이러한 검색 표 를 정적 검색 표 라 고 합 니 다.검색 과정 에서 검색 표 에 존재 하지 않 는 데이터 요 소 를 동시에 삽입 하거나 검색 표 에서 존재 하 는 데이터 요 소 를 삭제 하면 동적 검색 표 라 고 합 니 다.
기초 지식:

                  ：  
             ：  
typedef float KeyType;      //    
typedef int    KeyType;            //    
typedef char KeyType;            //      
         ：  
typedef struct {  
         KeyType   key;               //      
         ........                               //     
}SElmType;  
                 ：  
//         
#define EQ(a, b)    ((a) == (b))  
#define LT(a, b)     ((a) < (b))  
#define LQ(a, b)     ((a) > (b))  
 //          
#define EQ(a, b)    (!strcmp((a), (b)))  
#define LT(a, b)     (strcmp((a), (b)) < 0)  
#define LQ(a, b)     (strcmp((a), (b)) > 0) 

구체 적 인 분석:
1. 순서 찾기.
       순서 찾기: 표 의 마지막 기록 부터 하나씩 기록 한 키워드 와 주어진 값 을 비교 합 니 다. 만약 에 특정한 기록 의 키워드 와 주어진 값 이 같 으 면 찾 은 기록 을 찾 습 니 다.반대로 첫 번 째 기록 까지 키워드 와 주어진 값 이 같 지 않 으 면 표 에서 찾 은 기록 이 없고 찾 는 데 성공 하지 못 했 음 을 나타 낸다.
       성능 분석: 우 리 는 한 프로그램의 성능 을 토론 할 때 보통 세 가지 측면 에서 시간 복잡 도, 공간 복잡 도, 그리고 알고리즘 의 다른 성능 을 알 고 있다.찾 는 과정 에서 보통 고정된 크기 의 보조 공간 만 비교 해 야 하기 때문에 공간의 복잡 도 는 일정한 것 이다.시간 복잡 도 는 가 변 적 이다. 키워드 와 주어진 값 을 비교 한 기록 개수 의 평균 값 이다.
      적용 범위: 순서 찾기 는 일반적으로 검색 데이터 가 비교적 적은 경우 에 적용 된다.
      장점:
      1. 알고리즘 실현 이 간단 하고 적응 범위 가 넓다.
      2. 표 의 구 조 는 아무런 요구 가 없고 기록 이 키워드 에 따라 질서 있 게 배열 되 든 안 되 든 상관없다.
      3. 순서 표 에 적합 하고 단일 체인 표 에 도 적용 된다.
     단점:
     1. 평균 검색 길이 가 비교적 크 고 특히 n 이 많 을 때 검색 효율 이 비교적 낮다.
     2. 속도 가 느 리 고 평균 검색 길 이 는 (n + 1) / 2 이 며 시간 복잡 도 는 O (n) 이다. 

typedef int ElementType;  
#define EQ(a, b)  ((a) == (b))  
  
int sequential(int Array[], ElementType key, int n)  
{  
    int index;  
    for(index = 0; index < n; index++){  
        if(EQ(Array[index], key))     
            return index + 1;  
    }  
    return -1;  
}  

2. 반반 으로 찾 습 니 다.
       절반 찾기: 절반 찾기 는 2 분 찾기 라 고도 부 르 며, 먼저 조사 대기 기록 이 있 는 범위 (구간) 를 확정 한 후, 이 기록 을 찾 거나 찾 지 못 할 때 까지 범 위 를 점차 좁 힌 다.
       적용 범위: 규모 가 큰 질서 표 찾기, 효율 이 높 습 니 다.거의 바 뀌 지 않 지만 자주 찾 는 시계 에 적합 합 니 다.
        장점:
       1. 반 으로 나 누 어 찾 는 효율 이 순서대로 찾 는 것 보다 높다.
       2. 반 으로 나 누 어 찾 는 시간의 복잡 도 는 log 2 (n) 이다.
       3. 반 으로 나 누 어 찾 는 평균 검색 길 이 는 log 2 (n + 1) - 1 입 니 다.
       단점:
       1. 반절 찾기 는 질서 표 에 만 적 용 됩 니 다.
       2. 반절 찾기 는 순서 저장 구조 에 국한 되 고 선형 링크 에 대해 효과적으로 반절 찾기 를 할 수 없다.    
       
        키워드 key 와 표 의 특정한 요소 array [i] 를 비교 하면 3 가지 상황 이 있 습 니 다.
        1. key = = array [i], 찾기 성공
        2. key > array [i], 요 소 를 찾 을 수 있 는 범 위 는 array [i] 이전 입 니 다.
        3. key < array [i], 원 소 를 찾 을 수 있 는 범 위 는 array [i] 다음

typedef int ElementType;  
#define EQ(a, b)  ((a) == (b))  
#define LT(a, b)  ((a) < (b))  
#define LQ(a, b)  ((a) <= (b))  
  
int Search_Bin(ElementType Array[], int num, int length)  
{  
    int index_low, index_mid, index_high;  
    index_low = 1;  
    index_high = length;  
    while(index_low <= index_high){  
        index_mid = (index_low + index_high) / 2;     
        if(EQ(num, Array[index_mid]))  
            return index_mid + 1;  
        else if (LT(num, Array[index_mid]))  
            index_high = index_mid - 1;  
        else  
            index_low = index_mid + 1;  
    }  
    return -1;  
}  

3. 블록 별로 찾기.
       블록 찾기: 블록 찾기 는 색인 순서 찾기 라 고도 부 르 며 순서 찾기 의 개선 방법 입 니 다.n 개의 데이터 요 소 를 '블록 에 따라 질서 있 게' m 블록 (m < = n) 으로 나 눕 니 다.모든 블록 에 있 는 데이터 요 소 는 질서 가 있 을 필요 가 없 지만 블록 과 블록 사이 에 '블록 에 따라 질서 가 있어 야 합 니 다'. 즉, 첫 번 째 빠 른 요소 의 키 워드 는 두 번 째 블록 에 있 는 모든 요소 의 키워드 보다 작 아야 합 니 다.그리고 두 번 째 블록 에 있 는 모든 요 소 는 세 번 째 블록 에 있 는 모든 요소 보다 작 습 니 다.    
        작업 단계:
       1. 각 속도 의 최대 키 워드 를 선택 하여 색인 표를 구성한다.
       2. 찾기 는 두 부분 으로 나 뉜 다. 먼저 색인 표를 2 분 검색 하거나 순서 로 찾 아 조사 대기 기록 이 어느 부분 에 있 는 지 확인한다.그리고 정 해진 속도 에서 순서 법 으로 찾 아 보 세 요.
      장점: 표 에 기록 을 삽입 하거나 삭제 할 때 이 기록 이 있 는 블록 을 찾 으 면 이 블록 에 삽입 하거나 삭제 연산 을 합 니 다 (빠 른 속도 로 무질서 하기 때문에 대량의 이동 기록 이 필요 하지 않 습 니 다).
      단점: 보조 배열 의 저장 공간 과 초기 표를 블록 으로 나 누 어 정렬 하 는 연산 을 추가 합 니 다.
      성능: 순서 찾기 와 2 분 찾기 사이 에 있 습 니 다.

#define MAX 3  
#define MAXSIZE 18  
  
  
typedef int ElemType;  
typedef struct IndexItem{  
    ElemType index;  
    int start;  
    int length;  
}IndexItem;  
IndexItem indexlist[MAX];  
  
ElemType MainList[MAXSIZE] = {22, 12, 13, 8, 9, 20, 33, 42, 44, 38, 24, 48, 60, 58, 74, 49, 86, 53};  
  
int sequential(IndexItem indexlist[], ElemType key)  
{  
    int index;  
    if(indexlist[0].index >= key) return 1;  
    for(index = 1; index <= MAX; index++){  
        if((indexlist[index-1].index < key)&&(indexlist[index].index >= key))   
                return index+1;  
    }  
    return 0;  
}  
  
int mainsequential(ElemType MainList[], int index, ElemType key)  
{  
    int i, num=0;  
    for(i = 0; i < index-1; i++){  
        num += indexlist[i].length;   
    }  
    for(i = num; i < num+indexlist[index-1].length; i++){  
        if(MainList[i] == key) return i+1;    
    }  
    return -1;  
}  

위 에서 소개 한 세 가지 검색 방법 을 제외 하고 질서 있 는 표 의 피 보 나치 찾기 와 삽입 값 찾기, 정적 트 리 표 찾기 도 있다.