탐색(search)

순차 검색(sequential search)

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

(리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때도 내부에서는 순차 탐색이 수행된다.)

 

색인 순차 검색(index sequential search)

색인순차 검색은 데이터가 정렬되어 있다는 가정하에 하는 것이다.

 

이진 검색(binary search) - '찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교'

이미 정렬된 데이터를 제외하면서(시작점 끝점을 중간점으로 옮겨서) 탐색(시작과 끝점의 중간점인 값과 타겟 비교하여)

정렬된 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄여가며 탐색 진행

def binary_search(array, target, start, end):
    # 원소가 없는 경우
    if start > end:
        return None
    mid = (start + end) // 2
    
    if array[mid] == target:
    	return mid
    # 타겟이 앞 쪽에 있는 경우
    elif array[mid] > target: # 중간점 이후는 타겟보다 모두 크므로
    	return binary_search(array, target, start, mid-1) # end를 mid-1로 대체
    # 타겟이 뒷 쪽에 있는 경우
    else: # 중간점 이전은 타겟보다 모두 작으므로
    	return binary_search(array, target, start, mid-1) # start를 mid+1로 대체

 

이진 탐색 트리(binary tree search)

typedef struct{
	char word[20];
    char mean[200];
}element;

typedef struct treeNode{
	element key;
    struct treeNode* left;
    struct treeNode* right;
}treeNode;

treeNode* searchDic(treeNode* root, element key){
	treeNode* p;
    int compare;
    p = root;
    
    while(p != NULL){
        compare = strcmp(key.word, p->key.word);
        if(compare<0) p = p->left;
        else if(compare>0) p = p->right;
        else printf("%s",p->key.word); return p;
    }
    return p;
}

 

보간탐색(interpolation search)