검색 알고리즘 - 선형 검색

선형 검색의 종료 조건

1) 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우 -> 검색 실패

2) 검색할 값과 같은 원소를 찾는 경우 -> 검색 성공!

 

배열 a가 있을 때 검색하는 프로그램은 다음과 같이 나타낼 수 있다.

i = 0
while True:
    if i == len(a):
    	# 검색 실패
    if a[i] == key:
    	# 검색 성공(찾은 원소의 인덱스는 i)
    i += 1

 

선형 검색 알고리즘 코드 1 (while)

# while 문으로 작성한 선형 검색 알고리즘

from typing import Any, Sequence

def seq_search(a: Sequence, key: Any) -> int: # 시퀀스 a가 있고 key는 아무 자료형, 결과는 int로 반환한다.
    """시퀀스 a에서 key와 값이 같은 원소를 선형 검색(while 문)"""
    i = 0

    while True:
        if i == len(a):
            return -1   # 검색에 실패하여 -1을 반환
        if a[i] == key:
            return i    # 검색에 성공하여 현재 검사한 배열의 인덱스를 반환
        i += 1

if __name__ == "__main__":
    num = int(input('원소 수를 입력하세요.: '))  # 배열 길이 num값을 입력받음
    x = [None] * num    # 원소 수가 num인 배열을 생성

    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))

    ky = int(input('검색할 값을 입력하세요.: '))  # 검색할 키 ky를 입력받음

    idx = seq_search(x, ky) # ky와 값이 같은 원소를 x에서 검색

    if idx == -1:
        print('검색값을 갖는 원소가 존재하지 않습니다.')
    else:
        print(f'검색값은 x[{idx}]에 있습니다.')

 

위 코드는 배열을 만들고, 배열에 숫자를 집어넣은 후 검색할 값을 입력받아 배열에 값이 들어있는지 검색하여 없으면 -1을 반환하고 있으면 발견한 인덱스를 반환한다.

반환된 값이 -1이면 없다는 것이고, -1이 아니면 검색에 성공한 것이기 때문에 반환받은 인덱스를 출력한다.

 

선형 검색 알고리즘 코드 2 (for문)

# for 문으로 작성한 선형 검색 알고리즘

from typing import Any, Sequence

def seq_search(a: Sequence, key: Any) -> int:
    """시퀀스 a에서 key와 값이 같은 원소를 선형 검색(for 문)"""
    for i in range(len(a)):
        if a[i] == key:
            return i    # 검색 성공(인덱스를 반환)
    return -1   # 검색 실패(-1을 반환)

위와 같이 for문으로 구현하게 되면 비약하게 라인 수가 짧아지는데 그냥 동일하다고 보면 될 것 같다.

return -1이 들어간 곳은 for문이 끝난 후까지 검색에 성공하지 못했기 때문에 모두 종료되어 -1을 반환한다.

 

선형 검색 알고리즘 코드 3 (실수 검색)

# seq_search( ) 함수를 사용하여 실수 검색하기
from ssearch_while import seq_search

print('실수를 검색합니다.')
print('주의: "End"를 입력하면 종료합니다.')

number = 0
x = []  # 빈 리스트 x를 생성

while True:
    s = input(f'x[{number}]: ')
    if s == 'End':
        break
    x.append(float(s))  # 배열 맨 끝에 원소를 추가
    number += 1

ky = float(input('검색할 값을 입력하세요.: ')) # 검색할 키 ky를 입력받기

idx = seq_search(x, ky) # ky와 값이 같은 원소를 x에서 검색
if idx == -1:
    print('검색값을 갖는 원소가 존재하지 않습니다.')
else:
    print(f'검색값은 x[{idx}]에 있습니다.')

 

선형 검색 알고리즘 코드 4 (다양한 데이터 검색)

# seq_search( ) 함수를 사용하여 특정 인덱스 검색하기

from ssearch_while import seq_search

t = (4, 7, 5.6, 2, 3.14, 1)
s = 'string'
a = ['DTS', 'AAC', 'FLAC']

print(f'{t}에서 5.6의 인덱스는 {seq_search(t, 5.6)}입니다.')
print(f'{s}에서 "n"의 인덱스는 {seq_search(s, "n")}입니다.')
print(f'{a}에서 "DTS의 인덱스는 {seq_search(a, "DTS")}입니다.')

 

보초법

선형 검색은 반복할 때마다 ① 배열의 끝까지 검색이 끝났는지, ② 찾는 키 값이 맞는지 2가지 종료 조건을 체크한다.

단순한 판단이지만 이 과정을 계속 반복하면 종료 조건을 검사하는 비용을 무시할 수 없다.

이 비용을 절반으로 줄이는 방법이 보초법이다.

 

보초법을 이용해 검색에 성공하는 경우와 검색에 실패하는 경우

검색할 값과 같은 원소를 발견해야 하므로 맨 끝에 도달했는지에 대한 판단은 필요하지 않다.

 

보초법의 핵심은 찾고자 하는 키 값을 배열의 맨 뒤에 삽입하고, 찾는 키 값이 맞는지만을 검사하는 것이다.

이로써 자동적으로 배열의 끝까지 검색이 끝났는지에 대한 조건은 비교하지 않게 되므로 반복문 내에서 종료 판단 횟수를 절반으로 줄일 수 있다.

 

보초법을 적용한 코드

# 선형 검색 알고리즘 코드 1 (while)을 보초법으로 수정

from typing import Any, Sequence
import copy

def seq_search(seq: Sequence, key: Any) -> int:
    """시퀀스 seq에서 key와 일치하는 원소를 선형 검색(보초법)"""
    a = copy.deepcopy(seq)  # seq를 복사
    a.append(key)   # 보초 key를 추가

    i = 0
    while True:
        if a[i] == key:
            break	# 검색에 성공하면 while문을 종료
        i += 1
    return -1 if i == len(seq) else i

if __name__ == "__main__":
    num = int(input('원소 수를 입력하세요.: '))  # num 값을 입력
    x = [None] * num    # 원소 수가 num인 배열을 생성

    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))

    ky = int(input('검색할 값을 입력하세요.: '))  # 검색할 키 ky를 입력받기

    idx = seq_search(x, ky) # 키 ky값과 같은 원소를 x에서 검색

    if idx == -1:
        print('검색값을 갖는 원소가 존재하지 않습니다.')
    else:
        print(f'검색값은 x[{idx}]에 있습니다.')