검색 알고리즘_선형 검색(linear search), 보초법

- 배열 검색방법 중 가장 기본

- 직선 배열에서 검색하는 경우에 원하는 데이터를 찾을때까지 맨 앞부터 순서대로 검색하는 알고리즘

---

목차

• 선형 검색의 종료 조건
• 보초법

---

1. 선형 검색의 종료 조건

 

 

2. 보초법(sentinel method)

 

선형검색의 종료 조건 검사 비용 감소 방법

원본 데이터 맨 끝에 검색할 값(보초)를 추가

종료 조건 1번이 필요 없으므로 판단 횟수 반으로 감소

스캔 종료 시 찾은 데이터가 원본 데이터인지 보초인지 구별 필요

 

from typing import Any, Sequence
import copy
 
""" 시퀀스 seq에서 key와 일치하는 원소 선형 검색(보초법) """
def seq_search(seq: Sequence, key: Any) -> int:
    a = copy.deepcopy(seq)  # seq 복사
    a.append(key)           # 보초 추가
 
    i = 0
    while True:
        if a[i] == key:     # 검색 값 찾으면 while문 종료
            break
        i += 1
    
    return -1 if i == len(seq) else i   # 검색 성공 : 인덱스, 검색 실패 : -1 return
 
if __name__ == '__main__':
    num = int(input('원소 수 입력 : '))
    x = [None] * num
 
    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))
 
    ky = int(input('검색할 값 : '))
 
    idx = seq_search(x, ky)
 
    if idx == -1:
        print('찾는 원소가 존재하지 않습니다')
    else:
        print(f'검색값은 x[{idx}]에 있습니다')