[자료구조] 탐색 2. 간단한 탐색들

앞에서 탐색과 맵에 대해 간략하게 설명했다.
정렬과 마찬가지로 탐색 역시 간단하게 구현할 수 있는 탐색 알고리즘들이 있는데, 그것들을 살펴보도록 하겠다.

---

1) 순차 탐색

처음부터 마지막 원소까지 모두 탐색하는 매우 단순하고 직관적인 탐색 알고리즘이다.
리스트 A와 탐색 키 key, 그리고 리스트에서의 탐색 범위 low~high가 주어진다면 그 어떤 테이블에서도 원하는 레코드를 찾을 수 있다.

def sequential_search(A, key, low, high):
    for i in range(low, high+1):
        if A[i] == key: # key값을 찾은 경우
            return i
    return None

그 어떤 테이블에서도 원하는 레코드를 찾을 수 있다는 장점이 있지만… 결국 n개의 요소를 모두 돌아야 하므로 O(n)의 시간 복잡도를 가진다. 그래서 간단하지만 차마 효율적이라고는 말할 수 없다.
그러나 탐색할 테이블이 정렬되어있지 않다면… 순차 탐색 외에는 다른 방법이 없다.

 

2) 이진 탐색

정렬된 테이블으로만 가능한 탐색이다. 테이블의 중앙값을 기준으로 테이블을 절반으로 나눈 후, 찾는 레코드가 중앙값보다 크다면 반으로 나눠진 오른쪽 리스트에서 다시 중앙값을 찾는 것을 반복한다. 반대로 찾는 레코드가 중앙값보다 작다면 왼쪽 리스트에서 다시 중앙값을 찾는 것을 반복한다.

def binary_search(A, key, low, high):
    if (low <= high):
        middle = (low + high) // 2
        if key == A[middle]:
            return middle
        elif key > A[middle]:
            return binary_search(A, key, middle+1, high)
        else:
            return binary_search(A, key, low, middle-1)
    return None

이진 탐색은 각 단계에서 탐색 범위가 반으로 줄어든다. 따라서 해당 알고리즘의 시간 복잡도는 O(log n)이다. 순차 탐색과 비교하면 굉장히 빨라진 모습을 보인다!
그러나 탐색하기 전에 반드시 테이블이 정렬되어 있어야 한다는 치명적인 단점을 가진다.

3) 보간 탐색

보간 탐색 역시 정렬된 테이블으로만 가능한 탐색으로, 탐색키가 존재할 위치를 예측하여 탐색하는 방법이다. 이진 탐색의 업그레이드된 버전이라고 생각하면 편하다. 이진 탐색에서는 중앙값을 항상 (low+high) / 2로 분할했었으나 보간 탐색에서는 중앙값을 low + (high-low) * (k-A[low] / A[high]-A[low])로 결정하는 형태이다.
책에서 150p를 펼치려고 한다. 이 때 우리는 1p부터 순서대로 150p까지 찾아가지 않는다. 책의 두께를 보고 150p가 될 법한 부분을 임의로 펼친 후 페이지를 150p와 비교한다. 그 다음에도 이러한 절차가 계속되는데, 이 양상과 보간 탐색이 굉장히 유사한 모습을 가진다.

def search_interpolation(A, key, low, high):
    if (A[low] <= key and A[high] >= key): # 이진과는 달리 조건식을 이렇게 새로 입력해 준다.
        middle = int( low + (high-low) * (key-A[low]) / (A[high]-A[low]) ) # 인덱스니까 int로 변환
        if key == A[middle]:
            return middle
        elif key > A[middle]:
            return search_interpolation(A, key, middle+1, high)
        else:
            return search_interpolation(A, key, low, middle-1)
    return None

본 알고리즘 역시 테이블을 분할하여 찾는 방식이라서 O(log n)의 시간 복잡도를 가진다. 그러나 통상적으로 이진 탐색보다 더 빠른 처리 속도를 보인다.

 

 

작성일자: 2023-03-12