python_선형검색알고리즘

선형검색이란

무작위로 늘어놓은 데이터 집합에서 검색을 수행하는 것.

원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘.

[종료 조건]

1. 검색 값을 찾지 못하고 맨 끝을 지나간 경우 (검색실패)
2. 검색 값과 같은 원소를 찾을 경우 (검색 성공)

원소의 개수가 n이라면 판단 횟수는 평균 n/2번

While문 사용

from typing import Any, Sequence

#seq_search() == 맨 처음 찾은 원소의 인덱스 변환 (없으면 -1)

def seq_search (a: Sequence, key: Any) -> int:
    #길이랑 같으면 -1
    #값을 찾으면 i
    i = 0
    while True:
        if i == len(a):
            return -1
        if a[i] == key:
            return i
        i += 1 
        
if __name__ == '__main__':
    num = int(input('원소 수 입력 : ')) 
    x = [None] * num #원소 수가 num인 배열 (None으로)
    for i in range(num): #num만큼
        x[i] = int(input(f'x[{i}] : ')) #원소 값 입력 
    
    key = int(input('검색 값 입력 : ')) 
    
    find_value = seq_search(x, key) #key와 같은 원소를 x에서 검색
    if find_value == -1:
        print('검색값을 갖는 원소가 존재하지 않습니다.')
    else:
        print(f'검색값은 x[{find_value}]에 있습니다.')

for문 사용

def seq_search (a: Sequence, key: Any) -> int:    
    for i in range (len(a)): #길이만큼
        if a[i] == key: #검색 성공
            return i
    return -1 #길이만큼 돌리므로 검색이 안되면 종료, 종료 시 -1 리턴

주의점

i += 1에서 증감연산자를 사용했더니 SyntaxError: invalid syntax 가 났다.

파이썬에서는 증감연산자를 제공하지 않는 것을 주의해야한다.