선형 검색 Linear Search

선형 검색 Linear search

시간 복잡도 : O(n), n은 데이터의 개수

선형 검색은 배열의 맨 앞부터 순서대로 원소를 스캔하는 방법이다. 원소가 정렬되지 않은 배열에서 검색을 할 때 사용하는 유일한 방법이다.

모든 원소를 앞에서부터 순차적으로 스캔하기 때문에 배열의 길이가 길면 시간복잡도도 증가하고 실제 실행 시간도 오래 걸린다.

다음과 같은 배열이 있다고 하자.

a = [1,5,3,4,7,2,8,9,0]

특정 숫자의 위치를 선형 검색으로 찾는 코드 예시이다.

a = [1,5,3,4,7,2,8,9,0]

n = int(input())
def lin_search(seq, n):

    i = 0
    while True:
        if i == len(seq):
            return f"{n}은 리스트에 없음"
            
        elif a[i]==n:
            return f'{n}은 {i+1}번째에 있음'
        i += 1

print(lin_search(a, n))

i는 인덱스를 나타내는 변수이다. 매번 i번째의 원소를 확인한 후 우리가 찾는 값과 같은지 아닌지를 검사한다. 같다면 검색 성공이고 아니라면 i를 1 증가시켜 확인 작업을 반복한다. 매 확인마다 우리가 배열의 마지막에 도달했는지 아닌지 역시 같이 판단한다. i와 배열의 길이가 같다면 마지막에 도달한 것이다. 배열의 맨 마지막에 도달 했는데도 찾는 값이 없다면 검색 실패이다.

즉 두 가지 조건이 충족되면 검색이 끝난다.

1. 원하는 값을 찾았는가 —> 검색 성공
2. 배열의 맨 마지막에 도달 했는가 —> 검색 실패

보초법 Sentinel method

위의 선형 검색 예시는 종료 조건이 두 개이다. 원하는 값을 찾았는가와 i의 값이 배열의 길이와 같은가이다. 두 번째 조건은 검색 실패를 의미한다. 보초법을 사용하면 두 번째 조건을 없앨 수 있다.

보초법은 리스트의 맨 마지막에 우리가 검색한 값을 추가한 후 선형 검색을 하는 방법이다. 맨 마지막에 추가한 값을 보초sentinel이라고 부른다. 원하는 값을 중간에 찾으면 기존의 선형 검색과 같지만, 찾는 값이 없어 맨 마지막에 도달할 경우 달라진다. 우리의 리스트의 맨 마지막 값은 우리가 찾는 값(보초)이므로 언제나 찾았다는 결론이 나온다. 종료 조건 두 개 중 후자가 필요 없어진다. 기존에 우리는 매 값을 확인한 후 지금이 리스트의 끝인지 아닌지를 판단해야만 했다. 하지만 이제는 리스트의 끝인지 아닌지를 확인할 필요가 없어진다. 판단 횟수가 절반으로 줄어드는 효과를 가져다 준다.

하지만 결론이 원래 있던 값인지, 아니면 우리가 추가한 보초인지를 판단해야 한다. 판단 횟수가 1회 늘어난다. 하지만 보통은 여전히 이득이다. 앞서 판단 횟수가 이미 절반으로 줄었기 때문이다.

import copy
a = [1,5,3,4,7,2,8,9,0]

n = int(input())
def lin_search(seq, n):

    i = 0
    b = copy.deepcopy(seq)
    b.append(n)

    while True:
        if b[i] == n:
            break
        i += 1
    return f"{n}은 리스트에 없음" if i==len(seq) else f'{n}은 {i+1}번째에 있음'

print(lin_search(a, n))