데이터 구조 (4) 찾기 알고리즘 (c 언어)

찾기 는 데이터 처리 가 자주 하 는 작업 입 니 다.여기 서 저 는 흔히 볼 수 있 는 몇 가 지 를 소개 합 니 다. 주로 정적 검색, 동적 검색, 해시 검색 이 있 습 니 다.
정적 찾기: 2 분 찾기, 순서 찾기, 삽입 값 찾기, 피 보 나치 찾기.
동적 검색: 주로 이 진 트 리 를 대상 으로 합 니 다.
하 쉬 찾기: 주로 하 쉬 가 찾 는 사상 을 이해한다.
첫 번 째: 2 분 찾기.
검색 영역 에서 중심 위 치 를 확인 한 후에 찾 아야 할 값 과 중심 값 을 비교 하면 전자 가 크 면 검색 영역 을 후반 부 로 잠 그 고 반대로 전반 부 에 잠 깁 니 다.이러한 과정 은 검색 영역 경계 가 끝 난 다 는 것 을 알 고 계속 진행 되 었 다.
순서 표 의 2 분 검색 프로그램 은 다음 과 같 습 니 다.
두 번 째: 순서 찾기
순서 찾기: 말 그대로 첫 번 째 부터 검색 구역 의 값 을 조사 대기 값 과 비교 하여 알 고 나 면 경계 가 끝 납 니 다.
프로그램 은 다음 과 같 습 니 다:
세 번 째: 플러그 인 찾기 
우 리 는 2 분 에 찾 아서 알 고 있 습 니 다. 반 으로 찾 는 것 입 니 다. 그러면 우 리 는 4 분 의 1 을 접어 서 찾 을 수 있 습 니까? 아니면 더 많은 것 을 찾 을 수 있 습 니까? 예 를 들 어 당신 은 영 한 사전 에서 'apply' 를 찾 을 수 있 습 니 다. 당신 은 반드시 책 을 넘 기 는 앞 이지 뒤에 있 는 것 이 아 닙 니 다.만약 "zoo" 를 찾는다 면, 너 는 책의 맨 뒤에서 부터 찾 을 것 이다. 중간 에서 찾 는 것 이 아니 라.
예 를 들 어 수치 범위 가 1 ~ 10000 인 100 개의 요소 가 작은 것 부터 큰 것 까지 고 르 게 분 포 된 배열 에서 5 를 찾 으 면 우 리 는 아래 표 시 된 작은 것 부터 찾 고 삽입 값 을 찾 는 중심 사상 만 고려 해 야 하 는 것 이 아 닙 니까?
프로그램 은 다음 과 같 습 니 다:

//    
#include

int binsearch(int *ListSeq,int ListLength,int KeyData)
{
	int low = 0;
	int mid;
	int high = ListLength - 1;
	while(low <= high)
	{
		mid = (low + high)/2;
		if(KeyData < ListSeq[mid])
			high = mid -1;
		else if(KeyData > ListSeq[mid])
			low = mid + 1;
		else
			return mid;
	}
	return -1;
}

네 번 째: 피 보 나치 찾기
피 보 나 치 찾기 는 사실 2 분 검색 의 향상 알고리즘 이기 도 합 니 다. 2 분 검색 에 비해 보통 비교 해 야 할 key 값 과 제 min = (low + high) / 2 의 위 치 를 비교 합 니 다. 피 보 나 치 는 비교 결 과 를 세 가지 상황 으로 나 누 었 습 니 다.
1. 같다.
2, 크다, low = mid +1, k -= 2 ;
3, 작 음, high = high - 1, k - = 1;
사실 피 보 나치 가 찾 는 것 은 피 보 나치 수열 의 성질 을 이용 한 것 이다. 피 보 나치 수열 의 앞 뒤 두 수의 비례 는 금 비례 0.618 에 점점 가 까 워 지기 때문에 하나의 길이 가 금 으로 분할 될 수만 있다 면 분할 후의 부분 은 계속 금 으로 분할 되 고 순환 된다.
프로그램 은 다음 과 같 습 니 다:
다섯 번 째: 힐 찾기.
해시 표 (Hash) 가 무엇 입 니까?
우 리 는 아래 표 시 된 범위 가 비교적 큰 배열 을 사용 하여 요 소 를 저장 합 니 다.하나의 함수 (해시 함수, 해시 함수 라 고도 함) 를 설계 하여 모든 요소 의 키 워드 를 하나의 함수 값 (즉, 배열 아래 표) 과 대응 하 게 할 수 있 습 니 다. 그래서 이 배열 유닛 으로 이 요 소 를 저장 합 니 다.또한 키워드 에 따라 모든 요소 로 '분류' 한 다음 에 이 요 소 를 해당 하 는 '클래스' 에 저장 하 는 것 으로 간단하게 이해 할 수 있다.그러나 각 요소 의 키워드 와 함수 값 이 일일이 대응 하 는 것 을 보장 할 수 없 기 때문에 서로 다른 요소 에 대해 똑 같은 함수 값 을 계산 할 가능성 이 높다. 그러면 '충돌' 이 생 긴 다. 다시 말 하면 서로 다른 요 소 를 똑 같은 '클래스' 로 나 누 는 것 이다.뒤에 우 리 는 충돌 을 해결 하 는 간편 한 방법 을 볼 수 있 을 것 이다.전체적으로 말 하면 '직접 주소 지정' 과 '충돌 해결' 은 하 쉬 표 의 두 가지 특징 이다.
해시 함수 가 무엇 입 니까?해시 함수 의 규칙 은 특정한 전환 관 계 를 통 해 키 워드 를 지정 한 크기 의 순서 구조 에 적당 하 게 분산 시 키 고 분 산 될 수록 나중에 찾 는 시간 복잡 도가 낮 고 공간 복잡 도가 높다 는 것 이다.알고리즘 사상: 해시 의 사고방식 은 매우 간단 하 다. 만약 에 모든 키 가 정수 라면 간단 한 무질서 한 그룹 을 사용 하여 실현 할 수 있다. 키 를 색인 으로 하고 값 은 그 에 대응 하 는 값 이다. 그러면 임의의 키 의 값 에 신속하게 접근 할 수 있다.이것 은 간단 한 키 의 경우 더 복잡 한 유형의 키 를 처리 할 수 있 도록 확장 합 니 다.알고리즘 프로 세 스: 1) 주어진 해시 함수 로 해시 표를 구성 합 니 다.2) 선택 한 충돌 처리 방법 에 따라 주소 충돌 해결;흔히 볼 수 있 는 충돌 해결 방법: 지퍼 법 과 선형 탐지 법.3) 해시 표 의 기초 위 에서 해시 찾기 를 실행한다.해시 표 는 시간 과 공간 을 저울질 하 는 대표 적 인 예 이다.메모리 제한 이 없다 면 키 를 배열 의 색인 으로 직접 사용 할 수 있 습 니 다.그러면 모든 검색 시간의 복잡 도 는 O (1) 입 니 다.시간 제한 이 없다 면 무질서 한 배열 을 사용 하여 순서대로 찾 을 수 있 습 니 다. 그러면 적은 메모리 만 필요 합 니 다.해시 시 계 는 두 극단 사이 에서 적당 한 시간 과 공간 을 사용 하여 균형 을 찾 았 다.해시 함수 알고리즘 만 조정 하면 시간 과 공간 에서 취사선택 할 수 있 습 니 다.복잡 도 분석: 단순 론 으로 복잡 도 를 찾 습 니 다. 충돌 이 없 는 Hash 표 의 경우 복잡 도 를 O (1) 로 찾 습 니 다. (주의, 찾기 전에 해당 하 는 Hash 표를 구축 해 야 합 니 다)Hash 를 사용 하면 우 리 는 무엇 을 바 쳤 습 니까?우 리 는 실제 프로 그래 밍 에서 대규모 데 이 터 를 저장 합 니 다. 가장 먼저 생각 나 는 저장 구 조 는 map 일 수 있 습 니 다. 즉, 우리 가 흔히 말 하 는 KV pair 입 니 다. Python 을 자주 사용 하 는 친구 들 이 이런 경험 을 할 수 있 습 니 다.맵 을 사용 하 는 장점 은 우리 가 데 이 터 를 후속 처리 할 때 데이터 의 키 에 따라 대응 하 는 value 값 을 신속하게 찾 을 수 있다 는 것 이다.맵 의 본질은 바로 Hash 표 입 니 다. 그러면 우 리 는 높 은 검색 효율 을 얻 은 토대 에서 무엇 을 바 쳤 습 니까?Hash 는 공간 으로 시간 을 바 꾸 는 전형 적 인 알고리즘 입 니 다. 예 를 들 어 원래 길이 가 100 인 배열 을 찾 으 려 면 해당 기록 을 옮 겨 다 니 고 일치 하면 됩 니 다. 공간 복잡 도 에서 볼 때 배열 이 by te 형식 데 이 터 를 저장 하면 이 배열 은 100 by te 공간 을 차지 합 니 다.현재 우 리 는 Hash 알고리즘 을 사용 합 니 다. 앞에서 말 한 Hash 는 반드시 규칙 이 있어 야 합 니 다. 제약 키 와 저장 위치의 관 계 를 가 져 야 합 니 다. 그러면 고정된 길이 의 hash 표 가 필요 합 니 다. 이때 도 100 byte 의 배열 입 니 다. 우리 가 필요 로 하 는 100 byte 가 키 와 위치의 관 계 를 기록 하 는 데 사용 된다 고 가정 하면 전체적인 공간 은 200 byte 이 고 규칙 을 기록 하 는 표 크기 는 규칙 에 따라크기 가 일정 하지 않 을 수도 있 습 니 다.
이상 은 검색 알고리즘 에 대한 소개 입 니 다. 동적 검색 에 대해 서 는 자세히 설명 하지 않 습 니 다.