탐색

*순차 탐색

// 정렬되지 않은 배열 arr의 순차탐색
int sequentialSearch(int arr[], int key, int low, int high)
{
    for (int i = low; i <= high; i++)
    {
        if (arr[i] == key)
            return i;
    }
    return -1; // 탐색 실패
}
 
// 오름차순으로 정렬된 배열 arr의 순차탐색
int sortedSequentialSearch(int arr[], int key, int low, int high)
{
    int i;
    for (i = low; i <= high; i++)
    {
        if (arr[i] > key)
            return -1;
        if (arr[i] == key)
            return i;
    }
    return -1; // 탐색 실패
}

*이진 탐색

// 재귀호출을 이용한 이진탐색 함수
int binarySearch(int arr[], int key, int low, int high)
{
    int middle;
    if (low <= high)                // 하나 이상의 항목이 있어야 탐색
    {
        middle = (low + high) / 2;
        if (key == arr[middle])        // 탐색 성공
            return middle;
        else if (key < arr[middle])    // 왼쪽 부분 탐색
            return binarySearch(arr, key, low, middle - 1);
        else                        // 오른쪽 부분 탐색
            return binarySearch(arr, key, middle + 1, high);
    }
    return -1;                        // 탐색 실패
}
 
// 반복문을 이용한 이진탐색 함수
int binarySearchIter(int arr[], int key, int low, int high)
{
    int middle;
    while (low <= high)
    {
        middle = (low + high) / 2;
        if (key == arr[middle])
            return middle;
        else if (key > arr[middle])
            low = middle + 1;
        else
            high = middle - 1;
    }
    return -1;
}

*색인 순차 탐색

;정렬되어있는 자료에 대한 인덱스 테이블(index table)을 추가로 사용하여 탐색 효율을 높인 검색 방법이다.

struct Index
{
    int key;    // 키 값
    int index;    // 키 값의 인덱스
};
// 색인 순차 탐색 함수
int indexedSearch(int arr[], int n, Index* tbl, int nTbl, int key)
{
    if (key < arr[0] || key > arr[n - 1])    // 키 값이 범위 밖
        return -1;
    for (int i = 0; i < nTbl; i++)
    {
        if (tbl[i].key <= key && tbl[i + 1].key > key)
            return sequentialSearch(arr, key, tbl[i].index, tbl[i + 1].index); // 순차 탐색
    }
    return sequentialSearch(arr, key, tbl[nTbl - 1].index, n);
}