데이터 구조 반절 탐색 법 (알고리즘 사상 과 소스 코드)

3090 단어 데이터 기구
I) 알고리즘 사상
         먼저, 표 중간 위치 에 기 록 된 키 워드 를 검색 키워드 와 비교 하고 이들 이 같 으 면 성공 적 으로 찾 습 니 다.그렇지 않 으 면 중간 위치 기록 을 이용 하여 시 계 를 앞, 뒤 두 개의 서브 시트 로 나 누고 중간 위치 기록 의 키워드 가 키 워드 를 찾 는 것 보다 크 면 앞의 서브 시트 를 찾 고 그렇지 않 으 면 뒤의 서브 시트 를 찾 습 니 다.     이상 의 절 차 를 반복 하여 조건 을 만족 시 키 는 결 과 를 찾 을 때 까지 찾 지 못 하면 실 패 를 되 돌려 줍 니 다.
Ⅱ) 소스 코드
#include
 
#define MaxSize 20
typedef struct
{
    int key;
}RecordType;
 
typedef struct
{
    int length;
    RecordType r[MaxSize + 1];
}RecordList;
 
int BinSearch(RecordList l, int key)
{
    int low = 1;
    int high = l.length;             //     
    int mid;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (key == l.r[mid].key)
        {
            return mid;              //      key == l.r[mid].key  mid  
        }
        else if (key < l.r[mid].key) 
        {
            high = mid - 1;          //   , high mid           
        }
        else
        {
            low = mid + 1;          //       
        }
    }
    return 0;
}
int main()
{
    RecordList L = { 10, 0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100};  //      
    printf("%d
"
, BinSearch(L, 30));       // 30     return 0; }

좋은 웹페이지 즐겨찾기