검색 알고리즘(Search Algorithm)의 선형 검색과 이진 검색 개념 정리

들어가며

어떠한 데이터 집합에서 원하는 값의 원소를 찾아내는 것을 검색이라고 하고, 이를 알고리즘으로 구현한 것이 바로 검색 알고리즘이다. 예를 들어, 우리가 주소록에서 누군가를 검색한다고 가정했을 때 다음과 같은 다양한 조건으로 검색할 수 있다.

• 성별이 남자인 사람
• 나이가 20세 이상인 사람
• 이름에 '영'자가 포함된 사람

위 검색 조건은 성별, 나이, 이름과 같이 특정 항목에 주목하고 있는데, 검색 알고리즘에서는 이를 키(key)라고 하며, 이는 대부분 데이터의 일부이다.

• 성별 : key와 일치하도록 지정
• 나이 : key가 포함되도록 범위 지정
• 이름 : key에 가깝도록 지정

가장 대표적인 검색 알고리즘으로는 배열 검색, 연결 리스트 검색, 이진 트리 검색이 있으나, 본 글에서는 배열 검색에 대해서만 정리하였다. 배열 검색은 또 다시 선형 검색, 이진 검색, 해시법으로 구분되며, 이들을 요약한 정보는 다음과 같다.

• 선형 검색 : 무작위로 늘어놓은 데이터 집합에서 검색 수행
• 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 집합에서 매우 빠른 검색 수행
• 해시법 : 데이터 추가 및 삭제가 빈번하게 발생하는 데이터 집합에서 매우 빠른 검색 수행

선형 검색

선형 검색은 직선 모양(선형)으로 늘어선 배열에서 특정 키를 검색하는 경우 배열의 맨 앞에서부터 특정 키를 찾을 때까지 순차적으로 검색하는 알고리즘으로, 데이터 집합이 배열일 때 가장 기본적인 검색 알고리즘이다. 만약 아래와 같은 배열이 있다고 가정해보자.

a = [1, 3, 4, 5, 7, 8, 11]

이 배열의 요소 중에서 5의 인덱스를 검색하는 과정은 다음과 같다.

1. 배열의 0 번째 인덱스 요소(1)와 검색하고자 하는 값(5)이 같은가? False
2. 배열의 1 번째 인덱스 요소(3)와 검색하고자 하는 값(5)이 같은가? False
3. 배열의 2 번째 인덱스 요소(4)와 검색하고자 하는 값(5)이 같은가? False
4. 배열의 3 번째 인덱스 요소(5)와 검색하고자 하는 값(5)이 같은가? True    → 종료

그렇다면 배열의 요소 중에서 존재하지 않는 12의 인덱스를 검색하면 어떻게 될까?

1. 배열의 0 번째 인덱스 요소(1)와 검색하고자 하는 값(5)이 같은가? False
2. 배열의 1 번째 인덱스 요소(3)와 검색하고자 하는 값(5)이 같은가? False
...
7. 배열의 6 번째 인덱스 요소(11)와 검색하고자 하는 값(5)이 같은가? False
8. 더 이상 검색 불가 → 종료

이와 같이 선형 검색이 종료되는 조건은 검색할 값을 찾은 경우(검색 성공), 검색할 값을 찾지 못한 경우(검색 실패)로 구분된다. 이를 코드로 나타내보면 다음과 같다.

def linear_search(data_set: list, key: any) -> int:
    i = 0
    while True:
        if i == len(data_set):
            return -1        # 검색 실패
        if data_set[i] == key:
            return i        # 검색 성공
        i += 1

if __name__ == '__main__':
    a = [1, 3, 4, 5, 7, 8, 11]    # 데이터 집합
    result = linear_search(a, 5)
    print(result if result > -1 else '검색실패')

위의 코드를 보면 알 수 있듯이 선형 검색은 반복할 때마다 검색 실패, 검색 성공을 판단하는 조건을 확인한다. 이는 단순한 판단에 불과하지만, 반복하는 과정에서 계속 실행되므로 종료 조건을 검사하는 비용이 누적된다. 즉, 데이터 집합의 규모가 커짐에 따라 종료 조건을 판단하는 비용 또한 계속 늘어나게 된다. 이와 같은 문제점을 해결할 수 있는 방법으로는 보초법이 있다. 보초법은 데이터 집합의 가장 마지막에 검색하고자 하는 키(보초)를 추가하여 선형 검색의 종료 조건 중 검색 실패에 해당하는 판단을 하지 않아도 된다. 위의 코드를 보초법으로 수정한 코드는 다음과 같다.

def linear_search(data_set: list, key: any) -> int:
    data_set = [x for x in data_set] + [key]
    i = 0
    while True:
        if data_set[i] == key:
            break            # 검색 성공
        i += 1
    return -1 if i == len(data_set) else i

if __name__ == '__main__':
    a = [1, 3, 4, 5, 7, 8, 11]    # 데이터 집합
    result = linear_search(a, 5)
    print(result if result > -1 else '검색실패')

이진 검색

이진 검색은 원소가 오름차순 또는 내림차순으로 정렬된 배열에서 보다 효율적으로 검색할 수 있는 알고리즘이다. 달리 말하자면, 검색 범위를 좁혀가며 원하는 값을 찾아내는 알고리즘이라고 할 수 있다. 즉, 이진 검색은 선형 검색에 비해 반복 횟수가 절반 이상으로 줄어들 수 있으므로 빠른 검색이 가능하다는 장점이 있다. 다만, 이진 검색을 사용하기 위해서는 먼저 배열의 데이터가 정렬되어 있어야 한다. 만약, 아래와 같은 배열이 있다고 가정해보자.

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

이진 검색은 배열의 왼쪽, 가운데, 오른쪽으로 구분하고, 가운데에 위치한 요소와 찾고자 하는 값의 크기를 비교하여 그 범위를 좁혀나간다.

index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
value	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
variable	left							center							right

위의 배열에서 14을 찾는 과정을 정리해보면 다음과 같다.

1. 중간 인덱스(왼쪽 + 오른쪽 // 2)에 위치한 요소(8)와 검색하고자 하는 값(14)이 같은가?
    → 검색하고자 하는 값이 더 크므로, 가운데에서 오른쪽으로 한 칸 이동한 값을 왼쪽으로 지정한다.

index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
value	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
variable									left			center			right

2. 중간 인덱스(왼쪽 + 오른쪽 // 2)에 위치한 요소(12)와 검색하고자 하는 값(14)이 같은가?
    → 검색하고자 하는 값이 더 크므로, 가운데에서 오른쪽으로 한 칸 이동한 값을 왼쪽으로 지정한다.

index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
value	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
variable													left	center	right

3. 중간 인덱스(왼쪽 + 오른쪽 // 2)에 위치한 요소(14)와 검색하고자 하는 값(14)이 같은가?
    → 검색하고자 하는 값과 일치하므로 검색 성공 → 종료

그렇다면, 배열의 요소 중에서 존재하지 않는 16의 인덱스를 검색하면 어떻게 될까?

1. 중간 인덱스(왼쪽 + 오른쪽 // 2)에 위치한 요소(8)와 검색하고자 하는 값(16)이 같은가?
    → 검색하고자 하는 값이 더 크므로, 가운데에서 오른쪽으로 한 칸 이동한 값을 왼쪽으로 지정한다.

index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
value	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
variable									left			center			right

2. 중간 인덱스(왼쪽 + 오른쪽 // 2)에 위치한 요소(12)와 검색하고자 하는 값(16)이 같은가?
    → 검색하고자 하는 값이 더 크므로, 가운데에서 오른쪽으로 한 칸 이동한 값을 왼쪽으로 지정한다.

index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
value	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
variable													left	center	right

3. 중간 인덱스(왼쪽 + 오른쪽 // 2)에 위치한 요소(14)와 검색하고자 하는 값(16)이 같은가?
    → 검색하고자 하는 값이 더 크므로, 가운데에서 오른쪽으로 한 칸 이동한 값을 왼쪽으로 지정한다.

index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
value	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
variable															left center right

4. 중간 인덱스(왼쪽 + 오른쪽 // 2)에 위치한 요소(15)와 검색하고자 하는 값(16)이 같은가?
    → 더 이상 우측으로 이동 불가하므로 검색 실패 → 종료

위의 예시를 보면 알 수 있듯이 이진 검색 알고리즘의 종료 조건은 a[center] == key인 경우 검색 성공, 검색 가능한 범위가 더 이상 없는 경우 검색 실패로 구분되며, 이를 코드로 나타내면 다음과 같다.

def binary_search(data_set: list, key: any) -> int:
    left = 0
    right = len(data_set) - 1
    while True:
        center = (left + right) // 2
        if data_set[center] == key:
            return center
        elif data_set[center] < key:
            left = center + 1
        elif data_set[center] > key:
            right = center - 1
           if left > right:
            return -1

if __name__ == "__main__":
    a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
    result = binary_search(a, 14)
    print(result if result > -1 else '검색실패')  

마치며

이렇게 선형 검색, 이진 검색에 대해서 정리해보았다. 이들은 다른 알고리즘을 배울 때 이해를 돕는 개념이므로 반드시 이해해야 한다. 다음에는 이어서 해시법에 대해서 정리하겠다.