탐색 (Searching)

n개의 원소들이 저장된 배열에서 특정 원소 x를 찾는다고 할때, 여러 가지 탐색(Search) 방법이 존재한다.

Linear Search

---

배열의 첫 번째 원소부터 차례대로 하나씩 x와 같은지 비교하는 방식으로 가장 간단한다. 시간복잡도는 \(O(n)\) 이다.

구현

int search(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x)
            return i;
    }
    return -1;
}

Binary Search

---

일단 배열의 원소들을 정렬한다. 그 후 반복적으로 배열을 반으로 나누어 x가 위치한 곳을 좁혀나가는 방식이다. 상당히 유용하게 사용되는 탐색 방법이다. 정렬하는데 \(O(nlog_2n)\)의 시간이 걸리지만, 탐색하는데에는 \(O(log_2n)\) 밖에 걸리지 않는다.

구현

int binarySearch(int arr[], int n, int x) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (arr[mid] == x)
            return mid;

        if (arr[mid] > x)
            r = mid - 1;
        else
            l = mid + 1;
    }
    return -1;
}

Jump Search

---

배열을 정렬한 후, 고정된 간격으로 넘어가면서 원소들을 검사하는 방식이다. x가 존재할 수 있는 구간을 찾으면 해당 구간을 선형 탐색한다. 고정된 간격 \(m\)을 얼마로 하느냐에 따라 시간복잡도가 달라진다. 최악의 경우 \((n/m+m-1)\) 번의 비교 연산을 하므로 비교 연산을 최소로 하려면 \(m=\sqrt{n}\) 으로 해야 한다. 시간복잡도는 \(O(\sqrt{n})\)이다.

구현

int jumpSearch(int arr[], int n, int x) {
    int sqrtn = (int)sqrt(n);
    int step = sqrtn;

    int prev = 0;
    while (arr[min(step, n - 1)] < x) {
        prev = step;
        step += sqrtn;
        if (prev >= n)
            return -1;
    }

    for (int i = prev; i <= min(step, n - 1); i++) {
        if (arr[i] == x)
            return i;
    }
    return -1;
}

Interpolation Search

---

배열의 값들이 균일하게 분포된 배열에서 binary search 보다 빠르게 동작할 수 있는 탐색법이다. binary search는 항상 가운데 값을 검사하는데 반해, interpolation search는 선형보간법을 이용하여 검사할 위치를 찾는다. 원소들이 균일하게 분배되어 있다면 \(O(log_2{log_2n})\)의 시간복잡도를 가지지만, 최악의 경우 \(O(n)\)의 시간복잡도를 가진다.

구현

int interpolationSearch(int arr[], int n, int x) {
    int lo = 0, hi = n - 1;

    while (lo <= hi && arr[lo] <= x && x <= arr[hi]) {
        int pos = lo + (((double)(hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo]));
        
        if (arr[pos] == x) return pos;

        if (arr[pos] < x)
            lo = pos + 1;
        else
            hi = pos - 1;
    }
    return -1;
}

Exponential Search

---

정렬된 배열의 앞부분부터 크기가 1인 부분 배열의 끝을 조사하고, 그 다음 크기가 2인 부분 배열의 끝을 조사하고, 그 다음은 4, 8, .. 이런 식(doubling)으로 부분 배열의 끝이 x보다 커질 때까지 반복한다. 그 후에 x가 존재하는 부분 배열(을 binary search로 찾는다(마지막으로 조사한 위치를 i라고 하면, i/2 와 i 사이를 찾아보면 된다). 시간복잡도는 \(O(log_2n)\)이다.

Exponential Binary Search는 배열의 경계가 존재하지 않을 때, 즉 배열의 크기가 무한한 경우 유용하게 사용할 수 있고, 찾고자 하는 원소가 배열의 앞쪽에 위치할 경우, Binary Search 보다 빠르게 동작한다. 

구현

int exponentialSearch(int arr[], int n, int x) {
    if (arr[0] == x) return 0;

    int i = 1;
    while (i < n && arr[i] <= x) {
        i *= 2;
    }

    return binarySearch(arr, i / 2, min(i, n), x);
}

Ternary Search

---

Binary Search와 유사하지만, 다른 점은 매번 배열을 3등분하는 지점을 검사하여, x가 위치한 곳을 좁혀나가는 방식이다. 시간복잡도를 계산해보면 최악의 경우 Binary Search 보다는 느리지만, 유니모달 함수에서의 최댓값, 최솟값을 찾는데 유용하게 사용된다.

구현

int ternarySearch(int arr[], int n, int x) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid1 = (2 * l + r) / 2;
        int mid2 = (l + 2 * r) / 2;

        if (arr[mid1] == x) return mid1;
        if (arr[mid2] == x) return mid2;

        if (arr[mid1] > x) {
            r = mid1 - 1;
        }
        else if (arr[mid2] < x) {
            l = mid2 + 1;
        }
        else {
            l = mid1 + 1;
            r = mid2 - 1;
        }
    }
    return -1;
}

참고 자료

• http://quiz.geeksforgeeks.org/linear-search/
• http://quiz.geeksforgeeks.org/binary-search/
• http://www.geeksforgeeks.org/jump-search/
• http://www.geeksforgeeks.org/interpolation-search/
  
• https://en.wikipedia.org/wiki/Linear_interpolation
  
• http://www.geeksforgeeks.org/exponential-search/
• http://www.geeksforgeeks.org/binary-search-preferred-ternary-search/
• https://en.wikipedia.org/wiki/Ternary_search
  
• https://en.wikipedia.org/wiki/Unimodality