[algorithm] 선형탐색과 이진탐색 (Linear search and Binary)

선형 탐색

• 직선(선형)모양으로 늘어선 배열에서 검색하는 경우에 원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 순서대로 검색하는 알고리즘.
• 값이 많아질수록 탐색 시간도 길어진다.

20을 찾는 선형탐색

구현

from typing import Any, Sequence


def linear_search(a: Sequence, key: Any) -> int:
    i = 0
    for i in range(len(a)):
        if a[i] == key:  # 찾는 값을 발견했다면
            return i  # 인덱스 값 반환

    return -1

 

보초법 

한번의 검색을 할때마다 2가지 종료 조건을 체크하는 선형탐색의 탐색비용을 줄이기 위해 나온 방법으로 선형탐색의 비용을 절반으로 줄여준다.

 

보초법 수행 방법

1. 기존의 배열을 복사한다. (이때 복사는 deepcopy로 한다)
2. 복사한 배열의 마지막 부분에 찾고자하는 키값을 추가한다. 이때 추가한 값은 "보초값" 이라고 한다
3. 보초값에 도달하기 전에 키값을 찾았다면 그 값의 인덱스를 반환하고 보초값에 도달했다면 -1 을 반환한다.

이때 선형탐색은 "키값을 찾았는가?" 와 "검색할 값을 찾지 못하고 배열을 지나갔는가" 를 판단하는 반면에 보초법을 사용하면 두번째 조건은 사용할 필요가 없다.

 

코드

def seq_search(seq: Sequence, key: Any) -> int:
    a = copy.deepcopy(seq)
    a.append(key)

    i = 0
    while True:
        if a[i] == key:
            break
        i += 1
    return -1 if i == len(seq) else i

---

이진 탐색

이진탐색(Binary search)이란 정렬되어있는 배열에서 선형탐색보다 빠르고 효율적으로 원하는 값을 찾아낼 수 있는 방법이다. 업다운 게임을 생각하면 이해하기 쉽다.

 

위 그림은 9개의 값으로 이루어진 배열에서 23을 찾는 과정이다

 

1. 배열에서 중앙값(16)을 설정한다

2. 찾고자 하는 값이 오른쪽에 있다면 중앙값 왼쪽의 값들을 모두 제외한다(중앙값 포함), 왼쪽에 있다면 오른쪽을 제외한다.

3. 이 과정을 반복하다 키값이 나오면 종료한다.

 

코드

from typing import Any, Sequence

def binary_search(a: Sequence, key: Any) -> int:
    pl = 0  # 배열의 처음
    pr = len(a) #배열의 마지막

    while True:
        pc = (pl + pr) // 2  # 중앙 원소
        if a[pc] == key:  # 검색 성공
            return pc
        elif a[pc] < key:
            pl = pc + 1  # 중앙값 왼쪽 제외
        else:
            pr = pc - 1   # 중앙값 오른쪽 제외
        if pl > pr:  # 탐색 실패
            break
        return -1

 

선형 탐색과 이진 탐색 비교

선형 탐색의 시간복잡도 : O(n)

이진 탐색의 시간복잡도 : O(log n) 

이진탐색은 반복할때마다 탐색할 값이 절반씩 줄어드므로 시간복잡도가 log n 이 된다.

 

 

참고 : Do It 자료구조와 함께 배우는 알고리즘 입문 파이썬 편