데이터 구조 반절 탐색 법 (알고리즘 사상 과 소스 코드)
3090 단어 데이터 기구
먼저, 표 중간 위치 에 기 록 된 키 워드 를 검색 키워드 와 비교 하고 이들 이 같 으 면 성공 적 으로 찾 습 니 다.그렇지 않 으 면 중간 위치 기록 을 이용 하여 시 계 를 앞, 뒤 두 개의 서브 시트 로 나 누고 중간 위치 기록 의 키워드 가 키 워드 를 찾 는 것 보다 크 면 앞의 서브 시트 를 찾 고 그렇지 않 으 면 뒤의 서브 시트 를 찾 습 니 다. 이상 의 절 차 를 반복 하여 조건 을 만족 시 키 는 결 과 를 찾 을 때 까지 찾 지 못 하면 실 패 를 되 돌려 줍 니 다.
Ⅱ) 소스 코드
#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;
}