데이터 구조의 찾기 (2) - 순서 표 찾기

784 단어 데이터 구조
순서 찾기
순차 검색 (Sequential Search) 은 선형 검색 이 라 고도 부 르 는데 가장 기본 적 인 검색 기술 입 니 다. 이 검색 과정 은 표 의 첫 번 째 (또는 마지막) 기록 부터 하나씩 기록 한 키워드 와 주어진 값 을 비교 하 는 것 입 니 다. 만약 에 특정한 기록 의 키워드 와 주어진 값 이 같 으 면 찾 은 기록 을 성공 적 으로 찾 습 니 다.마지막 (또는 첫 번 째) 기록 까지 키워드 와 주어진 값 이 다 를 때 까지 표 에서 찾 은 기록 이 없어 서 찾 을 수 없습니다.
순서 찾기 알고리즘 의 시간 복잡 도 는 O (n) 입 니 다.
순서 찾기 알고리즘
//    ,a   ,n         ,key        (        1  )
int Sequential_Search(int *a, int n, int key) {
	for (int i = 1; i <= n; i++) {
		if (a[i] == key) {
			return i;
		}
		return 0;
	}
}

순서 찾기 최적화
//    ,a   ,n         ,key        
int Sequential_Search2(int *a, int n, int key) {
	//         
	int i = n;
	//  a[0]     ,     “  ”
	a[0] = key;
	while (a[i] != key) {
		i--;
	}
	return i;
}

좋은 웹페이지 즐겨찾기