[자료구조](22)[탐색 알고리즘 구현]

 

배열로 구현하기

크기가 100인 배열이라 하겠다.

 

Linear search

int linear(int arr[], int n, int key){
    for (int i = 0; i<MAX_SIZE; i++){
        if (arr[i] == key) {return i;}
    }
    rerturn -1;
}

 

Binary search

int binary(int arr[], int left, int right, int key){
    while (left <= right){ //left > right면 탐색 범위 벗어남 -> 종료
        int mid = left + (right - left) / 2; // 오버플로우 방지하며 mid 연산
        if (arr[mid] == key){
            return mid;
        }
        else if (arr[mid] < key){
            left = mid + 1; //off-by-one 오류 방지
        }
        else{
            right = mid - 1 //off-by-one 오류 방지
        }
    }
    return -1
}

 

Jump search

int jump(int arr[], int n, int key){
    int step = sqrt(n);
    int prev = 0; //이전 인덱스
    //key값을 넘어설 때까지 점프 뜀
    while (arr[(step < n ? step : n) - 1] < key){
        prev = step;
        step += sqrt(n);
        if (prev >= n){
            return -1; //다 뒤져봤는데도 없음
        }
    }
    while (arr[prev] < key){
        prev++;
        if (prev == step || prev >= n){ //범위 체크
            return -1;
        }
    }
    return (arr[prev] == key)? prev : -1; //찾았으면 인덱스 반환
}

 

Interpolation search

int interpolation(int arr[], int n, int ,key){
    //범위 체크 (low, high 관계, key가 low, high 사이인지)
    while ((low <= high) && (key >= arr[low]) && (key <= arr[high])){
        int pos = low + {(key - arr\[low])(high - low)} / (arr\[high] - arr\[low]);
        if (arr[pos] == key){
            return pos; //보간 탐색 성공
        }
        if (arr[pos] < key){
            low = pos + 1;
        }
        else{
            high = pos - 1;
        }
    }
    return -1;
}

 

Exponential search

int exponential(int arr[], int n, int ,key){
    if (arr[0] == key){ return 0;} //처음 인덱스 비교
    int i = 1;
    // 키의 값보다 클 때까지 지수적으로 범위 증가
    while (i<n && arr[i] <= key){
        i = i*2;
    }
    int left = i/2;
    int right = (i<n)? i : n-1;
    // 해당 범위 내에서 이진탐색
    int result = binary(arr, left, right, key);
    return result;
}

 

linked list로 구현

기존에 구현한 linked list 구조를 기반으로 하겠다.

 

linear search

Node* linear(Node* node, int key){
    while (node){
        if (node->data == key) {return node;}
        node = node->next;
    }
    return NULL;
}

 

sentinal linear search

Node* sentinal(Node* node, int key){
    if (!node) {return NULL;}
    Node* sentinal = makeNode(key);
    tail->next = sentinal; //연결리스트의 맨 끝인 tail 다음에 보초값 넣기

    Node* curr = node;
    while (curr->data != key){
        curr = curr->next;
    }
    tail->next = NULL;
    free(sentinal);

    //만약 맨 끝의 보초값을 찾았으면 free되어 NULL이 됨
    return (curr == NULL) ? NULL : curr;
}

 

Ternary search

U자 형태인지 n형태인지 잘 봐야 함.
여기에선 n자 형태로 peak값을 찾는 거

int ternary(int arr[], int size){
    int left = 0; right = size - 1;
    while(right - left > 2){
        int mid1 = left + (right - left)/3;
        int mid2 = right - (right - left)/3;
        if (arr[mid1] < arr[mid2]) {left = mid1 + 1;}
        else {right = mid2 - 1;}
    }
    int max_idx = left;
    for (int i = left + 1; i <= right; i++){
        if (arr[i] > arr[max_idx]) {max_idx = i;}
    }
    return max_idx;
}